Kotlin] 백준 1193번 문제풀이

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

 

풀이

(이 풀이는 기록용 풀이입니다 좋은 풀이가 아닙니다 ㅠ)

 

이 풀이는 시간이 좀 빡빡합니다.. 0.5초

 

그래서 반복문 내부에서 계속 배열을 만드는 작업을 하면 그만큼 시간을 먹어서 시간초과가 걸리므로 먼저 밖에서 분수의 배열을 만듭니다.

  

1을 만났을때 평이동을 했다는 증거로 false를 겁니다(그래야만 2를 만났을때 바로 평이동을 합니다). 그리고 가만보면 위로 가는 대각선이 있고, 아래로 가는 대각선이 있는데, 이를 구분하기 위한 변수도 미리 선언해둡니다.

 

이제 카운트 만큼 반복문을 돌립니다.

먼저 1/1 -> 2/1로 올라가기 때문에 두번째 값을 먼저 볼 수 있도록 조건문을 만들어야만 특수조건을 빼지 않을 수 있습니다.

이 때, 세로로 이동하는 평행값은 반드시 위로 올라가기 때문에 direction을 true로 만들고, 이미 평이동을 했기 때문에 평이동 변수도 true로 만들어줍니다.

다음은 평이동 함수를 거치지 않고, 비평이동 케이스로 이동하여, 위로 올라가는 값 그대로 0번째 값은 빼고 1번째 값을 더합니다.

그럼 1/2가 나옵니다. 평이동 변수는 false로 변경합니다.

다음 첫번째 값을 보면 1입니다. 이제 수평 이동을 합니다. 마찬가지로 평이동 케이스를 사용하며, 가로 이동을 했기 때문에 아래로 내려갑니다. direction은 false가 되고, 다시 평이동은 true가 됩니다.

그럼 1/3이 나옵니다.

다음은 평이동 함수를 거치지 않고, 비평이동 케이스로 이동하여, 아래로 내려가는 값 그대로 0번째 값은 더하고 1번째 값을 뺍니다.

그럼 2/2가 나옵니다. 평이동 변수는 false로 변경합니다.

1이 없기 때문에 그대로 평이동 함수를 거치지 않고, 비평이동 케이스로 이동하여, 아래로 내려가는 값 그대로 0번째 값은 더하고 1번째 값을 뺍니다.

그럼 3/1가 나옵니다. 평이동 변수는 false로 변경합니다.

 

이런식으로 평이동 변수와 방향변수를 잘 이용하여 함수를 짭니다.

 

fun main(args: Array<String>) {
    question1193()
}

fun question1193() {
    var count = readLine()!!.toInt()

    var fountain = "1/1"
    var fountainCount = fountain.split("/").map { it.toInt() }.toMutableList()

    // true : 정항뱡, false : 역방향
    var direction = true

    // true : 평이동 이미 됨, false : 평이동 안됨
    var parallel = false

    if (count != 1) {
        for (i in 2..count) {
            if (fountainCount[0] == 1 && !parallel) {
                fountainCount[1] += 1
                direction = true
                parallel = true
            } else if(fountainCount[1] == 1 && !parallel) {
                fountainCount[0] += 1
                direction = false
                parallel = true
            } else {
                if(direction) {
                    fountainCount[0] += 1
                    fountainCount[1] -= 1
                } else {
                    fountainCount[0] -= 1
                    fountainCount[1] += 1
                }
                parallel = false
            }

        }
    }

    fountain = fountainCount.joinToString("/")
    println(fountain)

}