[9095] 1,2,3 더하기

2017/07/01 - [코딩/알고리즘] - [2293] 동전1

이문제는 동전1과 같은 문제라고 생각해서 그렇게 풀었는데 아니었다.

동전1은 2+1과 1+2를 같다고 보지만,

이문제는 두개를 다른 경우로 보기때문이다.

사실 동전1에서두개의 포문 위치만 바꿔주면 된다.

구할 숫자에 대한 포문이 바깥이고 그 값을 1,2,3으로 만드는 경우의 수를 안쪽 포문으로 돌리면 

중복은 고려치 않고 1,2,3값을 계속 d[j]에 추가해주기 때문이다.

동전1에서는 1,2,3으로 만드는 경우의수 포문이 바깥에 있었기때문에 중복없이 경우의 수를 구할 수 있었다.

---

#include <cstdio>

using namespace std;

int main()

{

int N, T = 0;

int d[12];

scanf("%d", &T);

for (int k = 0; k < T; k++)

{

scanf("%d", &N);

for (int i = 0; i < 12; i++)

{

d[i] = 0;

}

d[0] = 1;

for (int j = 1; j <= N; j++)

{

for (int i = 1; i <= 3; i++)

{

if (j >= i)

{

d[j] += d[j - i];

}

}

}

printf("%d\n", d[N]);

}

}