[C++] Sakura Reflection (백준 30788번)

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

 

 

각도가 d인 축을 기준으로 대칭이동 시켰을 때 그림이 얼마나 회전하는지를 계산하기 위한 뻘짓...

그래서 식은 nxt = (2 * d - cur) % 360 이다.

(cur: 대칭이동 전의 그림의 각도, nxt: 대칭이동 후의 그림의 각도, d: 대칭이동 축의 각도)

 

이건 식 정리 과정...

그래서 정리하면 다음과 같다.

 

우선 그림이 원래 상태로 돌아오려면 대칭이동은 짝수번 시켜야 한다.

축이 홀수개이면 무조건 불가능하므로 생각해주지 않아도 된다. 

 

k번의 대칭이동 후의 그림의 각도는 2 * d(k) - 2 * d(k-1) + ... + 2 * d(2) - 2 * d(1) 가 된다.  (k는 짝수)

즉, 짝수 내에서와 홀수 내에서의 축의 배치 순서는 전혀 상관이 없고 짝수번째에 배치할지 홀수번째에 배치할지만 영향을 주는 것이다. 

 

그래서 이제 dp를 하면 되는데 식을 다음과 같이 세웠다.

dp[i][j][k]: i번째 축까지 사용했고 짝수번째로 사용한 축이 j개일 때 상태 k(0~359)가 가능한지

(여기서 상태는 그림의 각도이다. 즉 0 이상 359 이하의 정수이다.)

 

dp에는 무엇을 저장할까?

역추적이 필요없다면 가능한지(1) 아닌지(0)만 저장하면 될 것 같은데

이 문제에서는 역추적이 필요하므로 이전 상태를 저장해준다. 

이전 상태를 저장하기 위해서 직전 i, j, k를 모두 저장해줄 필요는 없고, 직전 j만 있어도 추적이 가능하다. 사용할 축의 순서는 정해져 있고 직전 축을 짝수로 썼는지 홀수로 썼는지만 알면 되기 때문이다. 

(처음에는 i, j, k를 모두 저장했다가 메모리 초과를 받았다.)

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> d(n + 1);
    for (int i = 1; i < n + 1; i++) cin >> d[i];

    // d가 홀수개이면 바로 종료
    if (n % 2 == 1) {
        cout << "NO\n";
        return 0;
    }

    // dp[i][j][k]: i번째 축까지 사용했고 짝수번째로 사용한 축이 j개일 때 상태 k(0~359)가 가능한지
    //              가능하다면 이전 상태(이전 j) 저장, 불가능하다면 -1 저장 (j만 저장해도 이전 상태를 추척할 수 있음)
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n / 2 + 1, vector<int>(360, -1)));

    dp[0][0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            for (int k = 0; k < 360; k++) {
                if (dp[i][j][k] != -1) { // 가능한 상태라면
                    dp[i + 1][j][(k - 2 * d[i + 1] + 360) % 360] = j;
                    dp[i + 1][j + 1][(k + 2 * d[i + 1] + 360) % 360] = j;
                }
            }
        }
    }

    if (dp[n][n / 2][0] != -1) { // 마지막에 원상태로 돌아올 수 있다면
        vector<int> even;
        vector<int> odd;

        int ci = n;
        int cj = n / 2;
        int ck = 0;
        while (ci > 0) {
            int pj = dp[ci][cj][ck];
            if (cj == pj + 1) { // ci번째 축이 짝수번째로 사용되었으면
                even.push_back(ci);
                ck = (ck - 2 * d[ci] + 360) % 360;
            } else if (cj == pj) { // ci번째 축이 홀수번째로 사용되었으면
                odd.push_back(ci);
                ck = (ck + 2 * d[ci] + 360) % 360;
            }
            ci--;
            cj = pj;
        }

        cout << "YES\n";
        int tmpn = n / 2;
        for (int i = 0; i < tmpn; i++) cout << even[i] << ' ' << odd[i] << ' ';
        cout << '\n';
    } else { // 불가능하다면
        cout << "NO\n";
    }
}

(AC)

 

---

 

[참고]

https://swoon1.tistory.com/33

https://hy3ons.tistory.com/40