백준 2602번 : 돌다리 건너기

  LCS 개수 찾기의 약간 어려운 버전이라고 보면 될 것 같다. 완전히 LCS 식으로 생각해보자면 두루마리와 돌다리의 LCS의 갯수를 구하라는 문제다. 다만 돌다리를 번갈아가면서 밟아야 한다는 조건만 추가적으로 신경 써주면 된다.

---

  따라서 기본적인 알고리즘 flow는 LCS와 동일하다. 돌다리가 2개이기 때문에 angel_dp, devil_dp처럼 2차원 배열을 두 개로 둬도 되지만 나는 하나의 배열에서 하고 싶었기 때문에 3차원 배열을 사용했다. dp[n][k]의 정의는 다음과 같다.

 

k번째 돌다리까지 왔을 때 n번째 두루마리의 문자까지 만들 수 있는 경우의 수

 

  dp가 증가하는 조건은 단 한가지이다. 현재 살펴보고 있는 두루마리(scroll)의 위치에 있는 문자와 살펴보고 있는 돌다리(angel 또는 devil)의 위치에 있는 문자가 같을 때이다. 그 외에는 이전값을 그대로 가져오기만 하면 된다.

  같을 경우에는 번갈아가면서 건너야 한다는 조건 때문에 이전 값을 더하는 것이 아닌 다른 돌다리의 값을 더해야 한다. 예를 들어 자신이 angel 돌다리를 살펴보고 있었다면 devil 돌다리의 값을 더해하는 것이다.

 

#include <iostream>

using namespace std;

string scroll, angel, devil;
int dp[21][101][2];

int strlen(string str)
{
    int length = 0;
    while(str[length]) length += 1;
    return length;
}

int main()
{
    cin >> scroll >> angel >> devil;
    
    int scrollLen = strlen(scroll);
    int bridgeLen = strlen(angel);
    
    for(int j = 0; j <= bridgeLen; j++)
    {
        dp[0][j][0] = 1;
        dp[0][j][1] = 1;
    }
    
    for(int i = 1; i <= scrollLen; i++)
    {
        for(int j = 1; j <= bridgeLen; j++)
        {
            if(scroll[i-1] == angel[j-1]) dp[i][j][0] += dp[i-1][j-1][1];
            if(scroll[i-1] == devil[j-1]) dp[i][j][1] += dp[i-1][j-1][0];
            dp[i][j][0] += dp[i][j-1][0];
            dp[i][j][1] += dp[i][j-1][1];
        }
    }
    
    cout << dp[scrollLen][bridgeLen][0] + dp[scrollLen][bridgeLen][1];
    
    return 0;
}