백준 9095 1,2,3 더하기

<링크>

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

<dfs_소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include<stdio.h> int N; int dfs(int); int main() {     int T;     scanf("%d", &T);     while (T--)     {         scanf("%d", &N);         printf("%d\n",dfs(0));     } } int dfs(int sum) {     if (sum > N)         return 0;     if (sum == N)         return 1;     int cnt = 0;     for (int i = 1; i <= 3; ++i)     {         cnt+=dfs(sum + i);     }     return cnt; }

cs

<풀이>

dfs로 해도 되고, dp로 풀어도 된다.

n이 최대 10이기 때문에

dfs로 해도 되지만

n이 커지면 dp로 풀어야 된다.

<dp_소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include<stdio.h> int dp[11] = { 1, }; int main() {     for(int i=1;i<=10;++i)         for (int j = i - 1; j >= i - 3; --j)             if (j >= 0)                 dp[i] += dp[j];     int T,N;     scanf("%d", &T);     while (T--)     {         scanf("%d", &N);         printf("%d\n", dp[N]);     } } Colored by Color Scripter

cs

<풀이>

5를 만들수있는 경우의 수는

4에서 1을 추가한 경우,

3에서 2를 추가한 경우,

2에서 3을 추가한 경우

로 나타낼 수 있으므로

4를 만드는 경우의 수 + 3을 만드는 경우의 수 + 2를 만드는 경우의 수이다.

앞에서부터 쭉쭉 만들어나가면 된다.