문제
70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까? baekjoon
코드
#include <iostream>
#include <vector>
using namespace std;
long long go(vector<vector<long long>> &v, int f, int h) {
if (v[f][h] != -1) return v[f][h];
if (f == 0) return 1;
if (h == 0) return v[f][h] = go(v, f - 1, h + 1);
return v[f][h] = go(v, f - 1, h + 1) + go(v, f, h - 1);
}
int main() {
while (true) {
int n;
cin >> n;
if (n == 0) break;
vector<vector<long long>> v(n + 1, vector<long long>(n + 1, -1));
cout << go(v, n, 0) << endl;
}
}
풀이
한 조각을 꺼내면 f - 1개, h + 1개가 되고 반 조각을 꺼내면 h - 1개가 된다.