3159 전구

도저히 생각나지 않아서 솔루션을 찾아봤다.

1.

xx010xx   xx010xx   xx101xx   xx101xx

xx010xx   xx101xx   xx010xx   xx101xx

이 경우에 중간에 있는 세로 두개만 바꾸는게 변환횟수를 최소화 하는 방법

2.

xx01xx

을 만나면 +1

저걸 보고 나서 직접 해보니 저게 최소한의 횟수를 구하는 방법인 건 알겠지만 이상하게 납득이 안간다. 나중에 다시 풀어봐야겠다.

#include <iostream>
#include <string>
using namespace std;
 
int n, ans;
string s[2];
 
int main() {
    cin >> n;
    for (int i = 0; i < 2; i++) {
        cin >> s[i];
        s[i] = '0' + s[i] + '0';
    }
    for (int i = 0; i < n; i++) {
        if (((s[0][i] == '0' && s[0][i + 1] == '1' && s[0][i + 2] == '0') || (s[0][i] == '1' && s[0][i + 1] == '0' && s[0][i + 2] == '1')) &&
            ((s[1][i] == '0' && s[1][i + 1] == '1' && s[1][i + 2] == '0') || (s[1][i] == '1' && s[1][i + 1] == '0' && s[1][i + 2] == '1'))) {
            s[0][i + 1] ^= 1;
            s[1][i + 1] ^= 1;
            ans++;
        }
        if (s[0][i] == '0' && s[0][i + 1] == '1') ans++;
        if (s[1][i] == '0' && s[1][i + 1] == '1') ans++;
    }
    cout << ans << '\n';
    return 0;
}