[백준 2602] 돌다리 건너기 C++

2602번: 돌다리 건너기

돌대가리 건너기

다이나믹 프로그래밍

 

처음에 너무 어렵게 생각했다.. dp배열을 2차원으로 두고 별의별 조건들을 걸면서 했더니 머리만 아프고 문제는 예제입력조차 풀리지 않았다..

 

결국 어쩔 수 없이 구글을 참고했는데..

 

단순히 3차원 dp배열을 설정해주면 아주 쉽게 풀리는 문제였다

dp[현재 돌다리 상의 위치][다리 종류(천사or악마)][지금까지 밟은 문자열 개수]

 

처음 dp배열을 -1로 초기화 시켜주고

현재 dp값은 현재 돌다리 상의 위치로 부터 갈 수 있는 모든 돌다리의 dp값을 더해줌

끝까지 방문했으면 +1을 리턴

마지막으로 시작하는 다리가 2종류이므로 각각의 결과를 더해주면 끝!

#include <iostream>
#include <cstring>
 
using namespace std;
 
int dp[101][2][21];
string Sq, Bridge[2];
 
int solve(int now_idx, int now_b, int sq_idx){
    if(sq_idx == Sq.size()) return 1;
    
    int &ret = dp[now_idx][now_b][sq_idx];
    if(ret != -1) return ret;
    
    ret = 0;
    
    for(int i = now_idx; i < Bridge[0].size(); i++){
        if(Bridge[now_b][i] == Sq[sq_idx]){
            ret += solve(i+1, !now_b, sq_idx+1);
        }
    }
    
    return ret;
}
 
int main(){
    int result = 0;
    cin >> Sq >> Bridge[0] >> Bridge[1];
    
    memset(dp, -1, sizeof(dp));
    
    result += solve(0, 0, 0);   // 악마 먼저
    result += solve(0, 1, 0);   // 천사 먼저
    
    cout << result;
    
    return 0;
}

좀 더 열심히..하자