백준(BOJ) 9095번 1,2,3 더하기

문제 : https://www.acmicpc.net/problem/9095

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

나의풀이 :  

 n의 개수가 적기 때문에 완전탐색으로도 가능하나 동적 계획법 연습을 위해 동적계획법으로 풀어 보았다.

4를 시작으로 -1 을 빼는 경우 -2를 빼는 경우 -3을 빼는 경우로 나뉘어서 재귀적 함수를 호출한다. 

0이 만들어지면 경우의 수 1 반환, 0보다 작다면 0을 반환한다. 

중복되어서 계산되는 경우는 메모이제이션을 통해 중복 방지한다.

코드 ( C ++ ) 

#include <iostream>

#include <cstring>

using namespace std;

const int MAX = 10 + 1;

int cache[MAX];

int solve(int num)

{

if (num < 0) return 0;

if (num == 0) return 1;

int& ret = cache[num];

if (ret != -1)

return ret;

ret = 0;

ret += solve(num - 1);

ret += solve(num - 2);

ret += solve(num - 3);

return ret;

}

int main()

{

int C;

cin >> C;

while (C--)

{

memset(cache, -1, sizeof(cache));

int num;

cin >> num;

int result = solve(num);

cout << result << endl;

}

return 0;

}