BOJ 30788 - Sakura Reflection
문제 링크
문제 풀이
기하학 + DP 섞인 문제들을 풀다가... 만난.. 정말 어렵고.. dp에 관해 깨달음을 얻게 해 준 문제다.
일단, Sakura Reflection 표지로 생각하면 너무 어려우니까, 간단하게, 원에 화살표가 그려진 사진으로 생각해 보자.
0$^\circ$ 에서 179$^\circ $ 틀어진 축을 기준으로 대칭을 시키면, 그 사진은 회전과 동시에, 좌우 반전이 된다. 좌우 반전이 되지 않은 상태일 때, 회전된 각도는 0$ ^\circ$에서, 359$ ^\circ$ 만큼 되어 있을 수 있다. 자 그럼, 사진의 기울어진 정도에 따라 상태를 0에서 359라고 인덱싱 해보겠다.
그 기준은, 화살표가 보고 있는 방향이라고 생각하고 정의하면 편하다. 나는 오른쪽부터 반시계 방향으로 인덱싱을 해주었다.
좌우 대칭된 상태일 때도 화살표가 바라보는 방향을 해당 상태라고 생각해서 인덱싱 해준다. 이때 나는 인덱싱을 왼쪽부터 반시계 방향으로 해주었다.
자 그럼, 대칭이 되지 않은 상태 $X$에서, $D$만큼 기울어진 축으로 대칭을 시키면 인덱싱을 어떻게 변화시켜야 할까?
def mirror (X, d):
cnt = d - X + 360
return (X + 180 + cnt * 2) % 360
화살표가 상태, X를 바라보고 있을 때, 좌우대칭된 인덱싱은 X + 180을 바라보고 있고, X와 D 축이 떨어진 거리의 두 배를 X에서 이동하면 된다.
대칭된 상태에서, 다시 대칭이 되지 않은 쪽으로 인덱싱을 변화시킬 때도 똑같은 함수를 사용하면 된다.
이런 식으로, 같은 기울기 축$D$에 대해, 변수$x$ 이전 상태에서, $\text{mirror}(x, D)$ 로 변화시키는 $y=x$에 대칭인 상태 변화 함수를 만들었다.
이제 이 함수를 N번 사용해서, 원래상태 0을 다시 만들 수 있으면, 정답은 YES가 되게 된다.
나는 여기서 막혔다... 이 상태 변화 함수는 기준이 되는 축 $D$에 따라서, 180개의 상태에서 다른 180개의 고유한 상태로 일대일 대응되는 함수이다. 그냥, Dp를 어떻게 해야 될지 막막했다....
사실 이미 만들어 놓은 함수를 잘 보면, 특징들을 몇 개 발견할 수 있다.
함수를 잘 보면, 180을 계속 더해주고 있는데, 결국 짝수번 더하면, 360의 배수가 된다. 최종값에 상관이 없으므로, 빼도 된다.
def mirror (X, d):
cnt = d - X + 360
return (X + cnt * 2) % 360
자, 만약 0으로 되돌아갈 때 사용되는 축에 따라, 순열을 만들어 보자. $d_1$부터 $d_N$까지 차례로 연산을 적용해야 하는 시퀀스
$$D = \big[d_1, d_2, d_3, \cdots, d_N\big]$$
가 존재하여, $\text{mirror}( \text{mirror} ( \text{mirror} .... \text{mirror} (0, d_1), d_2), d_3) \cdots ) d_N)$ 의 값이 최종 상태의 값이라고 할 때, 해당 함수를 풀어서 전개해 보자!
초기 상태는 0이다. $d_1$을 적용하면, $mirror(0, d_1) = 2d_1 \mod 360$이다.
그 다음 $d_2$를 적용하면, $mirror(2d_1, d_2) = 2d_2 - 2d_1 \mod 360$,
그 다음 $d_3$를 적용하면, $mirror(2d_2 - 2d_1, d_3) = 2d_3 -2d_2 + 2d_1 \mod 360$ 이다.
최종적으로 $d_N$을 적용하면, 마지막 상태의 값은
$$\sum_{i=1}^{N} (-1)^{N-i}2d_i = 2d_N - 2d_{N-1} + 2d_{N-2} + \cdots + (-1)^{N-1}2d_1 \mod 360$$
가 되게 된다. 대칭을 적용하는 축의 기울기 순서는 짝수와 홀수만 상관이 있었고, 짝수 번째 기울기들은 서로 순서가 상관이 없고, 홀수 번째 기울기 또한, 순서가 상관이 없는 것을 알 수 있다.
자, 이것으로 무엇을 알 수 있냐? 우리는 각각의 축을 양수로 사용해야 할지, 음수로 사용해야 할지만 결정하면 된다. 축을 넣어가며, 현재 도달가능한 모든 상태에 대해, 음수와 양수로 각각 축을 사용하면서, 새롭게 전이해 주면 된다.
우리는 각 기울기 $d$에 대해, 모든 존재하는 값에, $2d$로 더해주거나, $-2d$로 더해주면서, $[0, 360)$ 상태 안에서 빙빙 돌면서, 냅색 디피를 통해 상태를 채우면서 $dp$를 해나가면 되는 것이다.
$\text{dp}[i][j][k] :$ 축을 사용해 대칭을 $i$번 했을 때, $j$번 양수 축을 사용하고, 상태가 $k$가 될 수 있으면 1 아니면 0이라고 정의한다. 이렇게 놓고 냅색 디피를 돌리면 된다.. 역추적도 들어가 있기 때문에 까다롭게 느껴질 수 있으나, dp전이 식은 굉장히 간단하기에, 역추적이 들어가 있어도 구현 난이도는 체감되지 않았다.
역추적 과정까지 하면, 우리는 해당 축을 양수번째로 사용할지, 홀수 번째로 사용할지 결정할 수 있는데, 양 수 아무 칸이나 넣고, 홀수 아무 칸에나 넣으면 된다.
시간복잡도는 $O(N^2K)$ 가 된다. $K=360$ 존재하는 상태의 갯수
#include<bits/stdc++.h>
using namespace std;
int dp[505][260][366], N;
int re[505][260][366];
int answer[505];
int POS = 1, NEG = 2;
void push (int step, int degree) {
for (int i=250;i>=0;i--) {
for (int j=0;j<=360;j++) {
if (dp[step][i][j]) {
int T = (j - degree * 2 + 720) % 360;
dp[step+1][i][T] = 1;
re[step+1][i][T] = j;
T = (j + degree * 2 + 720) % 360;
dp[step+1][i+1][T] = 2;
re[step+1][i+1][T] = j;
}
}
}
}
int main () {
cin >> N;
dp[0][0][0] = 1;
for (int i=0;i<N;i++) {
int x; cin >> x;
push(i, x);
}
if ((~N & 1) && dp[N][(N+1)/2][0]) {
int step = N;
int state = 0;
int used = (N+1)/2;
for (int i=0;i<N;i++) {
int newUSED = 0;
if (dp[step][used][state] == 1) {
answer[NEG] = step;
NEG += 2;
newUSED = used;
} else {
answer[POS] = step;
POS += 2;
newUSED = used - 1;
}
state = re[step][used][state];
used = newUSED;
step--;
}
cout << "YES\n";
for (int i=1;i<=N;i++) {
assert(1 <= answer[i] && answer[i] <= N);
cout << answer[i] << ' ';
}
} else {
cout << "NO\n";
}
}