[백준 9095] 1,2,3 더하기

문제

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

문제 설명

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

예제 입력

3
4
7
10

예제 출력

7
44
274

1을 만드는 방법 =  1가지

(1)

2를 만드는 방법 = 2가지

(1+1) / (2)

3을 만드는 방법 = 4가지

(1+1+1) / (1+2) / (2+1) / (3)

4를 만드는 방법 = 7가지

(1+1+1+1) / (1+1+2) / (1+2+1) / (1+3) / (2+1+1) / (2+2) / (3+1)

5를 만드는 방법 = 12가지

.....

3을 만드는 방법에서 예를 들면

1+1+1 에서 가장 앞 부분인 1을 제외하면

2를 만드는 방법의 가지수를 구해주면 2가지 이다.

이후 가장 먼저 2를 더할 때는 3-2의 값인 1을 만드는 경우의 수

3을 가장 먼저 더할때는 3을 만들 수 있는 경우의 수를 구하는 방식이다.

즉

dp[3] = 4 인 것을 구했다면

dp[4] 를 유추해 보자

dp[4] = 1 + dp[3]

  + 2 + dp[2]

  + 3 + dp[1]

임을 알 수 있으며 이는 4 + 2 + 1 = 7가지의 방법으로 4를 만들 수 있다.

이 점화식을 일반화 시키면 dp[n] = dp[n-1]+ dp[n-2] + dp[n-3] 이므로 이후 소스 작성은 어렵지 않을 것이다.

소스

// //  main.cpp //  DP // //  Created by seungwoo on 2018. 3. 27.. //  Copyright © 2018년 seungwoo. All rights reserved. // #include <iostream> #include <algorithm> using namespace std; int main(int argc, const char * argv[]) {          int testcase,n;     int dp[11]; //N<11     cin>>testcase;          // f(n) = f(n-1) + f(n-2) + f(n-3)     dp[1] = 1;     dp[2] = 2;     dp[3] = 4;     for(int i = 0; i<testcase; i++){         cin>>n; //정수 n         for(int j=4;j<=n;j++){             dp[j] = dp[j-1] + dp[j-2] + dp[j-3];         }         cout<<dp[n]<<endl;     }     return 0; }