백준 30788 - Sakura Reflection (Python)

문제 정보

• https://www.acmicpc.net/problem/30788
• DP, 역추적

---

문제 정리

앨범아트를 지나는 N개의 축이 주어지며, i번째 축이 수평선과 이루는 각도는 $A_i$이다. N개의 축을 각각 정확히 한 번 사용하여 대칭이동할 때, 앨범아트를 원래 상태로 만들 수 있는지를 찾고, 그 순서를 찾는 문제이다.

---

풀이

우선 회전각이 0~179도 제한이 있으므로, 홀수 번 회전할 경우, 반드시 좌우가 뒤집힌 상태가 되기 때문에 N이 짝수일 때만 보면 된다.

현재의 회전각을 $a$, 회전축 각도를 $r$이라고 두면, 대칭이동을 적용한 회전각은 다음과 같이 변한다.

• $(2r-a + 360) \mod 360$

이제 일반화를 해보자. 회전이 i번 적용되었을 때의 앨범아트의 회전각을 $a_i$, i번째 회전에 적용될 회전축 각도를 $r_i$이라고 하자.

• $a_0 = 0$
• $a_1 = (2r_1 + a_0 + 360) \mod 360$
• $a_2 = (2r_2 + a_1 + 360) \mod 360$
  ...
• $a_N = (2r_N + a_{N-1} + 360) \mod 360$

$a_N$은 N개의 축에 의해 대칭이 전부 적용된 회전각이므로 $a_0$과 같은 값이 되어야 하므로 0으로 볼 수 있다.
식을 정리해보면,

• $(2r_N - 2r_{N-1} + 2r_{N-2} - 2r_{N-3} + ... + (-1)^{N-1}\cdot2r_1) \mod 360 = 0$

과 같은 식이 나오게 된다. 여기서 알 수 있는 것은
-> 계수가 (+)인 항끼리 서로 교환 가능하고, 계수가 (-)인 항끼리 서로 교환 가능하다.
-> 즉, N개의 축을 N/2개씩 짝수 항(-)에 들어갈 회전축, 홀수 항(+)에 들어갈 회전축으로 분배하여 위 식을 만족하는지 체크해주면 된다.
-> 이걸 기반으로 점화식을 세워보면, DP[i][j][k] = (i번째 회전축까지 사용했고 지금까지 짝수 항에 들어간 회전축 개수가 j개일 때, 각도 k에 접근 가능한지 여부)
로 정리할 수 있고, $O(360 * N^2)$으로 해결할 수 있다.

어떻게 보면 0-1 냅색 + 역추적 문제라 비슷하게 풀면 된다.

---

후기

최근 DP를 풀면서 DP 유형에 좀 자신이 붙었는데, 이 문제 보고 자신감이 박살나버렸다...

---

코드

# 백준 30788

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(N, angle):
    if N % 2 == 1:
        return [['NO']]

    evenMax = N//2
    DP = [[[-1] * 360 for _ in range(evenMax+1)] for _ in range(N+1)]
    DP[0][0][0] = 0

    # DP 계산
    for i in range(N):
        for j in range(evenMax+1):
            for curA in range(360):
                if DP[i][j][curA] != -1:
                    # 짝수쪽에 추가
                    if j < evenMax:
                        nextA = (curA + 2*angle[i] + 360) % 360
                        DP[i+1][j+1][nextA] = j
                    # 홀수쪽에 추가
                    if i - j <= evenMax:
                        nextA = (curA - 2*angle[i] + 360) % 360
                        DP[i+1][j][nextA] = j

    if DP[N][evenMax][0] == -1:
        return [['NO']]

    # DP 역추적
    traceback = [[], []]
    curA = 0
    curJ = evenMax
    for i in range(N, 0, -1):
        curDP = DP[i][curJ][curA]
        # 짝수에 넣은 경우
        if curDP != curJ:
            curA = (curA - 2*angle[i-1] + 360) % 360
            traceback[1].append(i)
            curJ -= 1
        # 홀수에 넣은 경우
        else:
            curA = (curA + 2*angle[i-1] + 360) % 360
            traceback[0].append(i)

    # 출력 정리
    result = []
    for i in range(N):
        result.append(traceback[i%2][i//2])

    return [['YES'], result]


def main():
    N = int(input())
    angle = list(map(int, input().split()))

    for i in solve(N, angle):
        print(*i)


main()