[도전 12일차] 돌다리 건너기 - KOI 고등부 풀이

※복습 : 

 

문제 : BOJ 2602 돌다리 건너기

 

문제 링크

 

사용 알고리즘 : DP

 

풀이:

전형적인 DP 문제다.

1. DP 정의를 하자.

DP(c, r, k) => c번째 열,r(0or1)번 행부터 문자열 끝까지 k번째 글자부터 채워 나갈 때 나올 수 있는 경우의 수

 

2. 점화식을 세우자

DP(c, r, k) = DP(c+1,r,k) + DP(c+1, !r, k+1)

단, DP(c+1,!r,k+1) 은 c번째 k번 행이 k번째 문자일 때만 적용된다.

 

3. 구현을 하자.

자열의 길이가 100 정도로 아주 작으므로 재귀함수 + 메모이제이션으로 구현하자. (직관적이다.)

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
string goal,s[2];
int DT[101][2][21];
int solve(int c,int r,int k){
    if(k>=goal.length()) return 1;
    if(c>=s[r].length()) return 0;
    if(DT[c][r][k])
        return DT[c][r][k];
    int ans=solve(c+1,r,k);
    if(s[r][c]==goal[k])
        ans+=solve(c+1,!r,k+1);
    return DT[c][r][k]=ans;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>goal>>s[0]>>s[1];
    cout<<solve(0,0,0)+solve(0,1,0);
}

 

풀이가 평화롭다. 힐링 되는 시간이었다.

 

기존에는 가장 효율적인 풀이만 찾았는데, 문제를 풀다보니 정말 많은 문제를 빠른 시간 안에 풀 실력을 갖추고 싶다면  오히려 직관적이지만 느린 풀이, 긴 풀이가 공부할 때 효율적이라는 것을 깨달았다.

 

물론 현재에 충실하고 싶다면 백준에서 다른 분들의 동적 계획법 코드를 보는 것을 추천한다.