BOJ 1819 불끄기

불끄기
(http://boj.kr/1819)

\(T\)의 제한이 작다는 부분에서 힌트를 얻었다.

우선 버튼의 순서는 중요하지 않다는 것은 당연하고,
같은 버튼을 두 번 이상 사용할 필요가 없다는 것도 당연하다.

그러면 이제 왼쪽부터 차례대로 이 버튼을 사용할지 말지를 결정하면 되는데,
이 부분을 DP로 결정한다.
여러 방법이 있겠지만, \(D_{ij}\)를 \(i\)번째 전구부터 \(T\)개의 상태가 \(j\)일 때, \(i\)번째 전까지 켜진 불의 개수로 정했다. (왜냐면, \(i\)번째 전구의 앞은 더 이상 바꿀 일이 없고, 앞으로 \(T\)개는 현재 영향을 미치는 범위다.)
\(j\)는 비트를 이용해 나타낼 수 있고, 버튼의 순서는 버튼을 눌렀을 때마다 기록해둬서 찾으면 된다.

비트를 사용하는 DP라는걸 알아채서 다행인데, 비트가 나오면 머리가 정리가 안 돼서 코드를 못 쓰겠다.

#include <bits/stdc++.h>
 
using namespace std;
 
int mp[60], db[7], d[60][400];
vector<int> chk[60][400];
 
int main() {
    int n, t;
    scanf("%d %d", &n, &t);
    for (int i = 0;i < n;++i)
        scanf("%1d", &mp[i]);
    int slot = 0;
    for (int i = 0, j = 1;i < t;++i, j *= 2) {
        int u;
        scanf("%1d", &u);
        slot += u * j;
 
        db[i] = j;
    }
    int ed = db[t - 1] * 2 - 1;
    for (int i = 0;i <= n;++i)
        for (int j = 0;j <= ed;++j)
            d[i][j] = 1e9;
    int st = 0;
    for (int i = 0;i < t;++i)
        st += db[i] * mp[i];
    d[0][st] = 0;
 
    for (int i = 0;i <= n - t;++i) 
        for (int j = 0;j <= ed;++j) {
            int up = j ^ slot, up2 = j, cnt = 0, cnt2 = 0;
            for (int k = i;k <= i + t;++k) {
                if (d[k][up] > d[i][j] + cnt) {
                    d[k][up] = d[i][j] + cnt;
                    chk[k][up] = chk[i][j];
                    chk[k][up].push_back(i + 1);
                }
                if (d[k][up2] > d[i][j] + cnt2) {
                    d[k][up2] = d[i][j] + cnt2;
                    chk[k][up2] = chk[i][j];
                }
                cnt += up & 1;
                cnt2 += up2 & 1;
                up /= 2;
                up += db[t - 1] * mp[k + t];
                up2 /= 2;
                up2 += db[t - 1] * mp[k + t];
            }
        }
 
    printf("%d\n", chk[n][0].size());
    for (int k : chk[n][0])
        printf("%d\n", k);
 
    return 0;
}