[백준] 1193번: 분수찾기 - Kotlin[코틀린]

문제

 

1193번: 분수찾기

 

---

풀이

 

지그재그 순서의 분수를 차례대로 나열하고 열 별로 살펴보면 규칙성을 찾을 수 있다.

 

 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

 

 1열의 분모 + 분자 = 2, 2열의 분모 + 분자 = 3인 것처럼 각 열마다 분자와 분모를 더하면 열의 값 + 1이 된다. 이 규칙을 활용해 입력받은 숫자가 몇 번째 열에 속하는지 계산할 수 있다.

 

 분모와 분자를 더한 값을 나타내는 sum 변수와 분수의 순번을 나타내는 tmp변수를 선언한다. while문을 통해 tmp가 입력받은 num보다 작을 때까지 tmp에 sum을 더해주고 sum은 1 증가해준다. while문이 종료하면 sum은 현재 열의 값 + 1이 되고 tmp는 현재 열 마지막 분수의 번호를 나타내게 된다. 예를 들어 7를 입력 받은 경우에 sum은 5가 되고 tmp는 10이 되는데 7번째 분수는 4열에 포함되고 4열의 마지막 분수는 10번째 분수라는 뜻이다.

 

 이 숫자들을 이용해 분자와 분모를 계산하면 되는데 홀수 열과 짝수 열을 나누어 처리해야한다. 홀수 열의 경우에는 첫번째 분수에서 마지막 분수가 될수록 분자는 감소하고 분모는 증가한다. 짝수 열의 경우에는 반대로 분자는 증가하고 분모는 감소한다.

 

 tmp가 해당 열의 마지막 분수이기 때문에 tmp에서 입력받은 값 num을 뺀 값을 이용하면 입력받은 번째의 분수를 찾을 수 있다. 짝수 열의 경우에는 tmp - num + 1이 분자가 되고 sum - 분자가 분모가 된다. 홀수 열에서는 반대로 tmp - num + 1 이 분모가 되고 sum - 분모가 분자가 된다. 7번째 분수의 경우 tmp - num + 1 = 10 - 7 + 1 = 4 와 sum - 4 = 5 - 4 = 1으로 1/4가 되는 것이다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()

    val top : Int // 분자
    val bottom : Int // 분모

    var sum = 1 // 분자와 분모의 합
    var tmp = 0 // 현재 순번

    while(tmp < num) { // 입력받은 숫자의 열 찾기
        tmp += sum
        sum++
    }

    if(sum%2 == 0) { // 짝수 열
        top = tmp - num + 1
        bottom = sum - top
    } else { // 홀수 열
        bottom = tmp - num + 1
        top = sum - bottom
    }

    bw.write("$top/$bottom")
    bw.flush()
    bw.close()
    br.close()
}