[백준] [01193] [코틀린] 분수찾기

문제

• 플랫폼 : 백준
• 번호 : 01193
• 제목 : 분수찾기
• 난이도 : Silver 5
• 첫째 줄에 분수를 출력
• 문제 : 링크

 

---

생각

대각선이 가로지르는 방향 단위로 라인(line)을 나눴다. 예를 들면 다음과 같다.

 

- 1번 라인 : 1/1

- 2번 라인 : 1/2 2/1

- 3번 라인 : 3/1 2/2/ 1/3

- 4번 라인 : 1/4 2/3 3/2 4/1

- 5번 라인 : 5/1 4/2 3/3/ 2/4 1/5

 

각 라인의 규칙을 일반화해보면 다음 규칙을 도출해낼 수 있다.

• i번 라인에는 i개의 분수가 있다.
• 짝수 라인은 분자 증가, 분모 감소하고, 홀수 라인은 분자 감소, 분모 증가한다.
• i번 라인의 분자, 분모의 합은 line + 1과 같다

 

입력받은 x가 몇 번째 line에 속해있는 지, 그리고 그 라인의 첫번째 숫자(이 글에서는 cursor라고 하겠다.)가 무엇인지를 찾아낸다면 위의 규칙을 적용해서 x가 특정 라인에서 몇 번째 위치에 있는 지 찾아낼 수 있을 것이다.

 

예를 들어 x가 14이고, x가 위치한 라인과 첫번째 요소(cursor)를 찾아내보면

cursor = 11, line = 5 인데 line 5는 홀수 라인이므로 분자가 증가한다. x는 5번 라인의 4번째 분수임을 특정할 수 있고, 2/4임을 알 수 있게 된다.

---

코드 풀이

라인, 커서 찾기

    val x = readInt()
    var cursor = 1
    var line = 0

    while (true) {
        cursor += line
        line += 1
        if (cursor <= x && x < cursor + line) break
    }

어떤 line에 위치한 분수의 갯수는 line 값과 같다.

매번 라인의 첫 번째 요소로 cursor를 가리키게 하려면, line을 증가시키기전에 cursor를 기존 line값 만큼 증가시키고 line을 1 증가시키면 된다.

 

계속 반복하다가, 커서가 x보다 작거나 같고, x가 다음 라인의 커서보다 작을 때까지만 반복하면 된다.

이렇게 하면 cursor와 line을 찾을 수 있다.

 

해당 라인의 몇 번째 요소인지 찾고 분자, 분모 찾아내 출력

    val a: Int // 분자
    val b: Int // 분모
    if (line % 2 == 0) {
        // 짝수라인 : 분자 증가, 분모 감소
        a = (x - cursor) + 1
        b = line - a + 1
    } else {
        // 홀수라인 : 분모 증가, 분자 감소
        b = (x - cursor) + 1
        a = line - b + 1
    }
    val sb = StringBuilder()
    sb.append(a).append('/').append(b)
    print(sb)

라인이 짝수이면 분자감소 분모 증가이고, 라인이 홀수이면 분자증가 분모 감소이다.

line 번호, cursor와 x의 차를 기준으로 분모/분자를 추론할 수 있다.

---

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder

fun main() {
    val x = readInt()
    var cursor = 1
    var line = 0

    while (true) {
        cursor += line
        line += 1
        if (cursor <= x && x < cursor + line) break
    }
    val a: Int // 분자
    val b: Int // 분모
    if (line % 2 == 0) {
        // 짝수라인 : 분자 증가, 분모 감소
        a = (x - cursor) + 1
        b = line - a + 1
    } else {
        // 홀수라인 : 분모 증가, 분자 감소
        b = (x - cursor) + 1
        a = line - b + 1
    }
    val sb = StringBuilder()
    sb.append(a).append('/').append(b)
    print(sb)
}

private fun readInt(): Int {
    var value = 0
    var input: Int
    while (true) {
        input = System.`in`.read()
        when (input) {
            10, 32 -> return value // 공백이나 개행자
            else -> value = value * 10 + (input - 48)
        }
    }
}