백준 12887, 경로 게임

개요

문제 링크
골드 5, DP
제거할 수 있는 유효지점의 최대 개수

---

접근

1. 현재 지점의 제거가능 여부를 새로운 2d array에 저장한다.
2. dp에는 현재 지점을 포함한 최대 제거 가능 지점 수를 저장한다. 만약 '#'이면 0을 저장한다.
3. 현재 지점을 제거하려면 앞반대쪽, 반대쪽, 뒤반대쪽에 #이 없어야 한다.

   // 가운데 아래를 제거할 수 없는 케이스
   XOO    OXO    OOX
   OOO    OOO    OOO
   // 가운데 아래를 제거할 수 있는 케이스
   OOO    OOO
   XOO    OOX

   즉, 2 X 2의 4개 점에서 가로 두 개만 제거할 수 있다. 대각선으로 제거해버리면 지나갈 수 없다.
4. 만약 2 X 2의 4개 점에서 모든 4개 점이 제거 가능해도 앞반대쪽이 제거 가능하다면 현재점을 제거할 수 없다.

   // 이런 식으로 길이 막혀버린다.
   OO --> AO --> AO
   OO     OO     OB

---

Pseudo code

for (세로)
    for (가로)
        if (제거가능)
            dp[i][j] = max(앞, 앞반대)
        if (제거불가능)
            continue
        if (앞반대=# || 반대=# || 뒤반대=#)
            continue
        if (앞반대만 제거가능)
            continue
        제거가능[i][j] = 1
        // 제거가능하므로 1추가
        dp[i][j]++

---

Source code

#include <bits/stdc++.h>
using namespace std;

int a[2][60], b[2][60];
int dp[2][60];

int main() {
    int m;
    cin >> m;
    string t;

    a[0][0] = 1;
    a[1][0] = 1;
    for (int i=0; i<2; i++) {
        cin >> t;
        for (int j=1; j<=m; j++)
            a[i][j] = (t[j-1]=='.');
    }
    a[0][m+1] = 1;
    a[1][m+1] = 1;

    dp[0][0] = 0;
    dp[1][0] = 0;
    for (int j=1; j<=m; j++) {
        for (int i=0; i<2; i++) {
            dp[i][j] = 0;
            if (!a[i][j])
                continue;
            dp[i][j] = max(dp[i][j-1], dp[1-i][j-1]);
            if (!a[1-i][j])
                continue;
            if (!a[1-i][j-1])
                continue;
            if (!a[1-i][j+1])
                continue;
            if (b[1-i][j-1] && !b[i][j-1])
                continue;
            b[i][j] = 1;
            dp[i][j]++;
        }
    }
    cout << max(dp[0][m], dp[1][m]);
}