[BOJ] 9095 - 1,2,3 더하기 (C++)

1. 알고리즘

DP문제

2. 전체 소스

#include <iostream> #include <vector> using namespace std; int main() { int arr[12] = { 0, }; int num; cin >> num; vector <int> v(num); for (int i = 0; i < num; i++) { cin >> v[i]; } arr[0] = 1; for (int i = 1; i < 11; i++) { if (i - 1 >= 0) { arr[i] += arr[i - 1]; } if (i - 2 >= 0) { arr[i] += arr[i - 2]; } if (i - 3 >= 0) { arr[i] += arr[i - 3]; } } for (int i = 0; i < num; i++) { cout << arr[v[i]] << endl; } }

1,2,3 으로만 더해서 만들 수 있는 방법의 수를 구하는 것으로, 아래 로직과 같이 풀면된다.
1로 만들 수 있는 경우의수는 : 1 (1개)
2로 만들 수 있는 경우의 수는 : 1,1 / 2 (2개)
3로 만들 수 있는 경우의 수는 : 1,1,1 / 1,2 / 2,1 / 3 (4개)
4로 만들 수 있는 경우의 수는 : 1, 1,1,1 / 1, 1, 2 / 2, 1, 1 / 1, 2, 1 / 2, 2 / 3, 1 / 4 (7개)
....
4번째있는 수를 구하기 위해서는 
1) 3으로 만들 수 있는 경우 각각에 +1를 ,
2) 2로 만들 수 있는 경우 각각에  +2를,
3) 1로 만들 수 있는 경우 각각에 + 3를
해주면 구할 수 있다.
마찬가지로 5, 6, 7... 11까지 위 방법 3단계로 나눠서 구할 수 있다. 

주의할점은 3으로 만들 수 있는 경우의 수는
1) 1로 만들 수 있는 경우에 + 2를, 
2) 2로 만들 수 있는 경우에 +1 를 
하면 3개 아니야? 할 수 있는데, (예외적으로) 0으로 만들 수 있는 경우의수에 +3 해서 구할 수 있기 때문에 경우의 수는 총 4개가 된다. 
즉 arr[0] = 1를 해주는 이유가 바로 이 이유다. 

3. 참고 사항

유사한 문제 :https://www.acmicpc.net/problem/11052

4. 문제

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