백준 2602번 돌다리 건너기

문제 링크입니다: https://www.acmicpc.net/problem/2602

처음에 조건을 너무 어렵게 생각해서 틀렸던 문제였습니다.

문자열의 길이는 '\n'까지 고려한다는 것을 숙지하고 있다면 기저사례를 쉽게 떠올릴 수 있습니다.

Top-Down 방식으로 재귀함수를 작성했기 때문에 쉽게 코드를 해석할 수 있을 것 같습니다.

(개인적으로 Bottom-Up 방식은 해석하기 너무 어렵기 때문에 Top-Down 방식을 선호합니다.)

#include <iostream>

#include <string>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 1;

const int SCROLLMAX = 20;

 

string scroll; //마법의 두루마리

string bridge[2];

int cache[2][MAX][SCROLLMAX];

 

int numOfWays(int col, int row, int idx)

{

        //기저 사례: 마법의 두루마리와 동일한 문자열을 모두 지났을 경우

        if (idx == scroll.length())

                 return 1;

 

        int &result = cache[col][row][idx];

        if (result != -1)

                 return result;

 

        result = 0;

        for (int i = row; i < bridge[0].length(); i++)

        {

                 //마법의 두루마리 인덱스에 적혀있는 문자와 해당 다리 인덱스에 적혀있는 문자 동일할 경우

                 if (bridge[col][i] == scroll[idx])

                         result += numOfWays(1 - col, i + 1, idx + 1);

        }

        return result;

}

 

int main(void)

{

        cin >> scroll;

        for (int i = 0; i < 2; i++)

                 cin >> bridge[i];

 

        memset(cache, -1, sizeof(cache));

 

        int result = 0;

        //천사 돌다리, 악마 돌다리 둘 중 하나에서 시작

        for (int i = 0; i < 2; i++)

                 result += numOfWays(i, 0, 0);

        cout << result << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~