[9095] 1, 2, 3 더하기

• 입력: 테스트 케이스 T 구하고자 하는 숫자 N
• 출력: 1, 2, 3으로 이용하여 표현할 수 있는 경우의 수 
• 예: 4를 표현한다고 하면 아래와 같은 경우의 수가 있다

1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1

• 알고리즘: 동적계획법, 피보나치 수열
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; int main() { int n, t; scanf("%d", &t); vector<int> dp(12, -1); dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i <= 11; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; for (int i = 0; i < t; i++) { scanf("%d", &n); printf("%d\n", dp[n]); } return 0; }

N = 1 일 때 경우의 수 1, N = 2일 때 경우의 수 1+1/2로 2, N = 3일 때 경우의 수 1+1+1/1+2/2+1/3 4가지이다.

이 때 위에 적은 4를 표현한다고 했을 때 N=3인 경우에 +1을 하는 것과 N=2인 경우에 +2을 하는 것과 N=3일 때 +3을 하는 것을 다 더하는 것과 같다. 

• 문제 참고: https://www.acmicpc.net/problem/9095