Codeforces Round #736 (Div. 2)-B. Gregor and the Pawn Game

문제 설명

$n \times n$ 크기의 체스판이 주어진다. 왼쪽부터 $i$번째 행과 $j$번째 열을 $(i, j)$ 라고 표기한다.

현재 조지는 $n$번째 행에 폰을 몇개 놓는다. 적 폰은 $1$번째 행에 위치해 있다. 각 턴마다 조지는 조지의 폰중 하나를 움직인다. 만약 맞은편에 폰이 존재하지 않는다면 폰은 위로 한칸 움직일 수 있다. $(i, j)$ 에서 $(i - 1, j)$ 추가적으로 위쪽 대각선에 상대 폰이 존재한다면 폰은 대각선으로 한칸 위로 움직일 수 있다. $(i, j)$ 에서 $(i - 1, j - 1) or (i - 1, j + 1)$ 그리고 그 위치에 있는 폰은 제거된다.

조지는 $1$번째 행에 자신의 폰이 최대 몇개나 위치할 수 있는지 알고싶다.

오직 조지의 턴만 가지고 있으며, 적 폰은 절대 움직이지 않는다. 또한 조지의 폰이 $1$번째 행에 위치한다면 그 폰은 절대 움직일 수 없다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 2 \cdot 10^4)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 체스판의 크기인 정수 $n (2 \le n \le 2 \cdot 10^5)$ 이 주어진다.

각 테스트케이스의 두번째 줄에는 길이가 $n$인 이진수로 이루어진 문자열이 주어진다. 만약 $i$번째 위치에 $1$이 있다면 왼쪽부터 $i$번째에 적 폰이 있다는 뜻이고, $0$이면 빈 공간이다.

각 테스트케이스의 세번째 줄에는 길이가 $n$인 이진수로 이루어진 문자열이 주어진다. 만약 $i$번째 위치에 $1$이 있다면 왼쪽부터 $i$번째에 조지의 폰이 있다는 뜻이고, $0$이면 빈 공간이다.

Output
각 줄마다 $1$번째 행에 자신의 폰이 위치할 수 있는 최대 개수를 출력한다.

Example
input
4
3
000
111
4
1111
1111
3
010
010
5
11001
00000

output
3
4
0
0

문제 접근

사용한 알고리즘: 그리디 알고리즘, 구현
걸린 시간 : 00:04
문제를 풀때는 1000정도 난이도를 가지고 있을 줄 알았는데, 풀고나서 보니까 800난이도 태그가 붙은 문제. 조금 쪽 팔렸다. 일단 먼저 알 수 있는 것은 $n$번째 열에 자신의 폰이 있는데 맞은편에 상대 폰이 없다면 무조건 채울 수 있다. 다른 방법은 존재하지 않는다.

그렇다면 $n$번째 열에 자신의 폰이 있는데, 그 열에 상대 폰이 있다면 현재 그 폰은 그 열로 움직일 수 없다. 그렇다면 그 양 옆에 폰이 있는지 확인하고 있다면 그 위치로 그리디하게 움직이면 된다. 이때 상대폰과 자기폰을 구분하기 위해서 다른 숫자로 채워주는 건 센스.

이때 양 대각선에 모두 상대 폰이 있다면 오른쪽이면 오른쪽으로 계속 일관되게 하던지, 왼쪽이면 왼쪽으로 계속 일관되게 폰을 움직여야 한다. 그게 각 위치에서 최선의 선택을 하는 그리디 알고리즘의 정의이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string a, b; cin >> a >> b;
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(b[i] == '0') continue;
            if(a[i] == '0') ans++, a[i] = '2';
            else{
                if(i > 0 && a[i - 1] == '1') ans++, a[i - 1] = '2';
                else if(i < n - 1 && a[i + 1] == '1') ans++, a[i + 1] = '2';
            }
        }
        cout << ans << "\n";
    }
    return 0;
}