백준 2602번 - 돌다리 건너기

www.acmicpc.net/problem/2602

2602번: 돌다리 건너기

KOALA의 이번 주 모의테스트 문제였다.

 

누가 봐도 DP 문제였다.

 

처음에 문제를 제대로 안 읽고 풀다가 시간을 많이 날렸다. 

돌다리의 길이가 최대 100인데 10으로 보고 풀다가.. 내 시간ㅠㅠ

 

핵심은 반드시 한 번씩 마법의 두루마리에 적힌 문자열을 모두 밟아야 한다는 것이다.

 

dp 문제의 핵심은 당연히 dp를 어떻게 정의하냐이다.

 

나는 dp[ i ][ j ][ k ]를 아래와 같이 정의했다.

 

마법의 두루마리에 적힌 문자열을 str이라 가정했을 때

str의 i번째 문자가 k 돌다리(이때 0은 천사, 1은 악마의 돌다리)의 j번째 칸에서 조건을 모두 지킨 경우의 수이다.

 

음..

내가 봐도 조금 복잡해 보이긴 하는데

쉽게 설명하면 dp에 내가 밟아야 하는 문자 순서대로 계산해서 저장해놓겠다 이 정도로 요약할 수 있을 것 같다.

 

중요한 점은 해당 칸을 계산할 때 천사의 돌다리면 악마의 돌다리를, 악마의 돌다리면 천사의 돌다리에서 정보를 가져와야 한다.

 

예제를 통해 살펴보자.

예를 들어 이번에 밟아야 하는 문자가 'G'이고, 악마의 돌다리에서 'G'가 발견되었고 4번째 칸이었다면

천사의 돌다리에서 3번째 칸까지 'R'이 나왔던 경우를 저장해놓은 것을 가져와야 한다는 의미이다.

 

설명이 많이 부실하지만.. 코드 보면 이해할 수 있을 거예요..

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    string str, angel, devil;
    cin >> str >> angel >> devil;
    ll dp[22][101][2]; // str, 돌다리 길이, angel or devil
    memset(dp, 0, sizeof(dp));
    for (ll i = 0; i < str.size(); i++) {
        char now = str[i];
        if (angel[0] == now) i == 0 ? dp[i][0][0] = 1 : dp[i][0][0] = 0;
        for (ll j = 1; j < angel.size(); j++) {
            if (i == 0) {
                dp[i][j][0] = dp[i][j - 1][0];
                if (angel[j] == now) dp[i][j][0]++;
            }
            else {
                dp[i][j][0] = dp[i][j - 1][0];
                if (angel[j] == now) dp[i][j][0] += dp[i - 1][j - 1][1];
            }
 
        }
        if (devil[0] == now) i == 0 ? dp[i][0][1] = 1 : dp[i][0][1] = 0;
        for (ll j = 1; j < devil.size(); j++) {
            if (i == 0) {
                dp[i][j][1] = dp[i][j - 1][1];
                if (devil[j] == now) dp[i][j][1]++;
            }
            else {
                dp[i][j][1] = dp[i][j - 1][1];
                if (devil[j] == now) dp[i][j][1] += dp[i - 1][j - 1][0];
            }
        }
    }
    ll size = angel.size() - 1;
    cout << dp[str.size() - 1][size][0] + dp[str.size() - 1][size][1] << "\n";
}

 

솔직히 줄이려면 더 간단하게 풀 수도 있을 것 같긴 했는데 아무래도 모의테스트 진행 중이다 보니..

 

int도 아마 맞긴 할 텐데 코드 포스에서 몇 번 데인 적이 있어서 그냥 안전하게 long long으로 바꿔 제출했다.

 

그리고 내가 include <bits/stdc++. h>를 처음 쓰고 올리는 포스팅이다. 

꼭 쓰세요 두 번 쓰세요