1193번: 분수찾기

문제 출처 : https://www.acmicpc.net/problem/1193

1193번: 분수찾기

언어 : Kotlin

 

문제 설명 :

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	...
2/1	2/2	2/3	2/4	...	...
3/1	3/2	3/3	...	...	...
4/1	4/2	...	...	...	...
5/1	...	...	...	...	...
...	...	...	...	...	...

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

• 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
• 첫째 줄에 분수를 출력한다.
•  

제한 사항 :

• 시간 제한 : 0.5초 (추가 시간 없음)
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
1	1/1
2	1/2
3	2/1
4	3/1
5	2/2
6	1/3
7	1/4
8	2/3
9	3/2
14	2/4

풀이 : 

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var x = br.readLine().toInt()
    var sum = 1
    var temp = 0

    while (temp < x) {
        temp += sum
        sum ++
    }

    if (sum % 2 == 0) {
        val a = temp - x + 1
        val b = sum - a
        bw.write("$a/$b")
    } else {
        val b = temp - x + 1
        val a = sum - b
        bw.write("$a/$b")
    }

    bw.flush()
    bw.close()
}

지그재그는 위와 같다.

각 대각선 라인마다 분자 + 분모는 동일하다.

각 대각선 라인별 시작지점 -> 끝지점의 규칙은 다음과 같다.

• 분자 + 분모가 짝수 = 시작 -> 끝으로 갈수록 분자-- 분모++
• 분자 + 분모가 홀수 = 시작 -> 끝으로 갈수록 분자++ 분모--