[백준] #15685: 드래곤 커브

1. Problem Link

• https://www.acmicpc.net/problem/15685

2. Solution

예제 입력 1 (Problem Link 참고)

• 0 : 1
• 1 : 2
• 2 : 3 -> 2
• 3 : 3 -> 0 -> 3 -> 2

즉, 3번째 커브에 대한 direction은 2번째 커브에 대한 direction (3 -> 2) 값에 1을 더해주고 4로 나눈 나머지 값에 대해 reverse를 취해준 결과(3 -> 0)와 원래 2번째 커브에 대한 direction (3 -> 2)를 이어줌으로써 얻을 수 있습니다.

3. Source Code

// ->, ↑, <-. ↓
val dx = listOf(1, 0, -1, 0)
val dy = listOf(0, -1, 0, 1)

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

    val n = br.readLine().toInt()
    val board = Array(101) { Array(101) { false } }
    repeat(n) {
        var (x, y, d, g) = br.readLine().split(" ").map { it.toInt() }
        // 0's direction
        board[y][x] = true
        x += dx[d]
        y += dy[d]
        board[y][x] = true

        // 1's direction
        d = (d + 1) % 4
        val directions = mutableListOf(d)
        
        for (i in 1..g) {
            // store (n-1)'s directions
            val temp = mutableListOf<Int>()
            temp.addAll(directions)

            // iterate
            for (direction in directions) {
                x += dx[direction]
                y += dy[direction]
                if (x !in 0..100 || y !in 0..100) continue
                board[y][x] = true
            }

            // n's directions
            val newDirections = directions.map { direction -> (direction + 1) % 4 }.reversed()
            directions.clear()
            directions.addAll(newDirections)
            directions.addAll(temp)
        }
    }

    var cnt = 0
    for (i in 0 until 100) {
        for (j in 0 until 100) {
            if (board[i][j] && board[i + 1][j] && board[i][j + 1] && board[i + 1][j + 1]) cnt++
        }
    }
    bw.write("$cnt")
    
    br.close()
    bw.close()
}

4. Complexity

• Time: O(N * G)
• Space: O(1)