[C++] 백준 2602번: 돌다리 건너기 - DP, DFS

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

2602번: 돌다리 건너기

dp + dfs로 문제를 해결했다.

일단 처음에는 돌의 개수 100개, 문자 개수 20개, 천사와 악마 시작으로 2개가 존재하길래 재귀를 이용한 완전 탐색으로 접근했다.

 

그런데 코드를 짜면서 볼때는 몰랐는데, 시간초과가 난다고 해서 급히 노선을 바꾸었다.

시간초과가 나는 이유는 나중에 알았는데 (질문),

돌 100개, 문자열 20개가 모두 같은 언어로 이루어지면

결국 2 * 100 C 20이 되기 때문이었다..

 

그래서 했던 생각이 천사 돌다리와 악마 돌다리 각각에 횟수를 저장하는 방법이다.

하지만 여기서도 문제가 생겼다.

가령 3번째 돌을 밟았는데, 해당 돌에 이미 횟수가 저장되어 있는 경우,

해당 숫자가 반지 문자열의 몇 번째 횟수인지 모르기 때문에

해당 문자가 몇 번째 문자열인지에 대한 정보도 저장해주어야했다.

 

쉽게 예를 들어,

입력으로

GSSS

GGGGSSSSS

RRRRSSSSS

가 주어졌을 때,

천사의 1번 G를 밟은 이후 악마의 2번 R을 밟을 것이다.

그 이후 다시 천사의 S를 밟을 것이고, 악마의 S를 밟을 것이다.

여기서 천사의 S에 정보가 들어가게 될텐데, 

이후에 천사의 2번째 G를 밟았을 때 S에 저장되어 있는 정보가 이전 탐색에서 저장했던 정보 중 몇 번째 S에 대한 정보인지 알아야했다.

그래서 angel, devil 두 배열을 만들고, 각각에 몇 번째 문자열에 대한 정보인지 기록하는 방식으로 코드를 짰다.

 

#include <iostream>
using namespace std;
int angel[101][101];
int devil[101][101];
string s, a, d;
int t, ans;
int dfs(int n, int t, bool c){
    if(t==s.length()) return 1;
    int sum=0;
    !c ? sum=angel[n][t] : sum=devil[n][t];
    if(sum) return sum;
    if(!c){
        for(int i=n; i<d.length(); i++){
            if(d[i]==s[t]){
                sum+=dfs(i+1, t+1, 1);
            }
        }
    }
    else{
        for(int i=n; i<a.length(); i++){
            if(a[i]==s[t]){
                sum+=dfs(i+1, t+1, 0);
            }
        }
    }
    return !c ? angel[n][t]=sum  : devil[n][t]=sum;
}
int main(){
    cin >> s >> a >> d;
    for(int i=0; i<a.length(); i++){
        if(a[i]==s[t]){
            angel[i][t]=dfs(i+1, t+1, 0);
        }
    }
    for(int i=0; i<d.length(); i++){
        if(d[i]==s[t]){
            devil[i][t]=dfs(i+1,t+1, 1);
        }
    }
    for(int i=0; i<a.length(); i++){
        ans+=devil[i][0]+angel[i][0];
    }
    cout << ans;
}

 

예전에 풀었던 욕심쟁이 판다 문제와 비슷하게 문제를 해결할 수 있었다.

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