백준 17675번 램프

문제 링크

참고 문헌

못 풀겠어서, 공식 풀이를 보고 AI로 번역해가며 풀었다.

첫번째 연산을 off, 두번째 연산을 on, 세번째 연산을 toggle 이라고 부르겠다.

이 문제는 세심한 관찰을 요구한다. 그것들을 나열해 보겠다.

1. off, on 연산들이 겹치지 않는 최적해가 항상 존재한다.
2. 모든 on, off 연산 이후에 모든 toggle 연산을 하는 최적해가 항상 존재한다.

관찰에 따라 모든 off, on 연산을 적용한 후에 toggle 연산을 적용할 것이다. 어느 한 위치에 대해 생각하면 그 위치에는 off 연산 또는 on 연산 또는 연산이 적용되지 않았을 것이다. 나이브하게 생각하면 $3^N$개의 모든 상태를 순회하고 toggle 연산만으로 해를 계산하면 된다. toggle 연산만 이용한 최적해는 $A \oplus B$ 에서 $1$ 이 연속한 구간의 개수이다.

dp를 통해 이 문제를 풀 것이다. dp의 상태는

1. 현재 위치
2. 현재 위치에 적용한 연산 (off, on, $\emptyset$)

이며, 값은 그 상태에서 최적해이다.

연산 횟수가 증가하는 경우는 다음 두 가지이다.

1. 현재 위치에서 off 또는 on 연산을 적용하는데, 이전 위치의 연산과 다를 때
2. 이전 XOR 값이 $0$이었는데, 현재 XOR 값이 $1$이 될 때

이에 따라 dp값을 계산하면 이 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1010101;

int n, dp[MAXN][3];
string a, b;

int main()
{
    cin >> n;
    cin >> a;
    cin >> b;
    a = '0' + a;
    b = '0' + b;
    dp[0][0] = dp[0][1] = 1e9;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 3; j++) {
            dp[i][j] = 1e9;
            for(int k = 0; k < 3; k++) {
                char p = (k==0 || k==2 && a[i-1]=='0' ? '0' : '1'); // i-1 == 0 이라면 항상 '0'
                char c = (j==0 || j==2 && a[i]=='0' ? '0' : '1');
                bool pxor = p != b[i-1];
                bool cxor = c != b[i];
                dp[i][j] = min(dp[i][j], dp[i-1][k] + (!pxor && cxor) + (j < 2 && j != k));
            }
        }
    }

    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
}