[ BOJ 백준 2602번 - 돌다리 건너기 ] 해설 및 코드

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

목적

두루마리의 문자열이 "RGS"라면 아래와 같은 돌다리는 다음 세가지 방법으로 건널 수 있다. 이러한 경우의 수를 구하자.

접근법

1. s[i][j][k]는 돌다리의 i번째 행, j번째 열이 두루마리의 k번째 문자와 같을 때의 가능한 경우의 수이다.

2. 메모이제이션을 이용하여 슥삭!

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
string key;
string stone[2];
int s[2][100][20];
 
int sol(int r, int c, int idx) {
    if (idx == key.length())return 1;
 
    int& ref = s[r][c][idx];
    if (ref != -1)return ref;
    
    ref = 0;
    f(i, c, stone[0].length())if(stone[r][i]==key[idx])    
        ref+=sol(!r, i + 1, idx + 1);
    
    return ref;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(s, -1, sizeof(s));
    cin >> key >> stone[0] >> stone[1];
    cout << sol(0, 0, 0) + sol(1, 0, 0);
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.