드래곤 커브 [백준 15685번]

문제

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

15685번: 드래곤 커브

 

내 풀이

 

전형적인 규칙 찾기 문제이다.

드래곤 커브가 만들어질 때 방향을 구해보면 규칙을 찾을 수 있다.

 

문제에 나온 예시로 규칙을 찾아보자.

0세대 : 0

1세대 : 0 1

2세대 : 0 1 2 1

3세대 : 0 1 2 1 2 3 2 1

4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

 

k세대에 새로 만들어지는 방향은 k-1세대의 방향들을 뒤집은 후 1을 더해주면 된다.

4세대를 예로 들어보겠다.

3세대 뒤집기 -> 1 2 3 2 1 2 1 0 -> 1을 더하기 -> 2 3 0 3 2 3 2 1 -> 3세대에 붙이기 -> 1 2 3 2 1 2 1 0 2 3 0 3 2 3 2 1

 

나는 딕셔너리를 사용하여 k세대의 방향을 저장하였다.

 

x축과 y축을 명명한 것이 평소에 내가 사용하던 방법과 달라서 좀 시간을 끌었다.

 

dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]
N = int(input())
board = [[0]*101 for _ in range(101)]
for _ in range(N):
    x, y, d, g = map(int, input().strip().split())
    dir = {0: [d]}
    for k in range(1, g+1):
        # k세대
        arr = dir[k-1] + [(x+1)%4 for x in dir[k-1]][::-1]
        dir[k] = arr
    board[y][x] = 1
    for i in dir[g]:
        x += dx[i]
        y += dy[i]
        board[y][x] = 1
ans = 0
for i in range(101):
    for j in range(101):
        if i+1 < 101 and j+1 < 101:
            if board[i][j] and board[i+1][j] and board[i][j+1] and board[i+1][j+1]:
                ans += 1
print(ans)

 

총평

규칙을 잘 찾아보자!