백준 2602번 돌다리 건너기

🔒문제 url

https://www.acmicpc.net/problem/2602

🔑알고리즘

• dp[i][j][k] : dp[악마,천사][돌다리 index][두루마리 index]
  
  현재의 다리(행)가 두루마리에 속한 단어(열)라면,
  경우의 수는 하나 직전의 단어가 적힌 다리를 밟은 횟수만큼 존재한다.
  예를 들어, 악마의 다리에 있는 S(다섯 번째 행)를 밟았다면 천사의 다리에 있는 G또한 밟았음을 의미한다.
  따라서, 천사의 다리에서 G를 밟을 수 있는 경우의 수만큼 더해줘야하므로 천사의 다리 dp 행렬에서 다섯 번째 행 이전, 두 번째 열의 값을 더한 값을 더하게 된다.
  
  
• 이를 점화식으로 나타내면 아래와 같다.
  • $dp[0][i][j] = dp[1][0 \leq k\lt i][j-1]$
    $if, devil[i] = target[j]$
    
    
  • $dp[1][i][j] = dp[0][0 \leq k\lt i][j-1]$
    $if, angel[i] = target[j]$
    
    
• 최종적으로 두 dp 배열의 모든 마지막 열 값의 합이 답안이 된다.

🐾부분 코드

//init
for (int i = 0; i < devil.length(); i++)
{
    if (devil[i] == target[0]) dp[0][i][0] = 1;
    if (angel[i] == target[0]) dp[1][i][0] = 1;
}

<dp 배열 초기화>
첫 번째 열이 유효하기 위해서는 반드시 두루마리의 첫 번째 글자와 일치해야함을 이용하여 배열을 초기화한다.

//dp
for (int i = 0; i < devil.length(); i++)
{
    for (int j = 1; j < target.length(); j++)
    {
        if (devil[i] == target[j])
        {
            int cnt = 0;
            for (int k = 0; k < i; k++)
                cnt += dp[1][k][j - 1];
            dp[0][i][j] = cnt;
        }

        if (angel[i] == target[j])
        {
            int cnt = 0;
            for (int k = 0; k < i; k++)
                cnt += dp[0][k][j - 1];
            dp[1][i][j] = cnt;
        }
    }
}

<dp 구하기>
위에서 설명한 점화식을 이용하여 dp 배열을 채운다.

//output
int ans = 0;
for (int i = 0; i < devil.length(); i++)
    ans += dp[0][i][target.length() - 1] +
           dp[1][i][target.length() - 1];
cout << ans;

<답 출력>
두루마리의 마지막 글자를 밟아야만 유효하므로, dp의 마지막 열 값을 모두 더한 후 출력한다.

🪄전체 코드

#include <iostream>
#include <string>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);

string target, devil, angel;
int dp[2][101][21];//{악마,천사} {돌다리 index} {두루마리 index}

void INPUT()
{
    IAMFAST
    cin >> target >> devil >> angel;
}


void solution()
{
    //init
    for (int i = 0; i < devil.length(); i++)
    {
        if (devil[i] == target[0]) dp[0][i][0] = 1;
        if (angel[i] == target[0]) dp[1][i][0] = 1;
    }

    //dp
    for (int i = 0; i < devil.length(); i++)
    {
        for (int j = 1; j < target.length(); j++)
        {
            if (devil[i] == target[j])
            {
                int cnt = 0;
                for (int k = 0; k < i; k++)
                    cnt += dp[1][k][j - 1];
                dp[0][i][j] = cnt;
            }

            if (angel[i] == target[j])
            {
                int cnt = 0;
                for (int k = 0; k < i; k++)
                    cnt += dp[0][k][j - 1];
                dp[1][i][j] = cnt;
            }
        }
    }

    //output
    int ans = 0;
    for (int i = 0; i < devil.length(); i++)
        ans += dp[0][i][target.length() - 1] +
               dp[1][i][target.length() - 1];
    cout << ans;
}

int main()
{
    INPUT();
    solution();
}

🥇문제 후기

입력값의 범위가 커질 경우, 누적합을 통해 최적화할 수 있으므로 참고하자.

문제도 어려웠고, 네 문제 연달아 푼 덕에 체력적으로도 힘들어서 너무 너무 오래 걸린(2시간 정도?) 문제다.
여전히 DP는 Gold 하위만 되도 빠르게 해결할 자신이 없다.🥲
양으로 때려박아서 쌓은 DP 경험이 아니었다면 절대로 못 풀었을 문제...
왜 새벽 5시야... 자야지..