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

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

 동적계획법 문제를 풀어보기 위해서 백준 사이트에 있는 9095번 문제를 풀어보기로 했습니다.

 문제의 내용은 정수 n을 받아서 n을 1,2,3 세 개의 합으로 나타내는 방법의 수를 구하는 문제입니다.

 예를 들어서 1은 1 (1가지)

 2는 1+1, 2 (2가지)

 3은 1+1+1, 1+2, 2+1, 3 (4가지)

 4는 위에 있는 것처럼 7가지입니다.

 처음에 어떻게 풀어야 될지 고민하다가 1,2,4,7 로 가지수가 증가하는 것을 보고 무슨 규칙이 있을 것 같아서 찾아보기로 했고 마침내 규칙을 발견하였습니다.

 4의 경우에는 1에 3을 더하는 방법, 2에 2를 더하는 방법, 3에 1을 더하는 방법의 수로 구할 수 있고 마찬가지로 N의 경우에는 N-1 에 1을 더하는 방법, N-2에 2를 더하는 방법, N-3에 3을 더하는 방법의 가지 수의 합으로 구할 수 있다.

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 27

#include <iostream> using namespace std; int dp[12] = { -1, }; int main(void) {     ios::sync_with_stdio(false);     cin.tie(NULL);     ///////////////////          dp[1] = 1;     dp[2] = 2;     dp[3] = 4;     for (int i = 4; i < 12; ++i) {         dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];     }          int tCase;     cin >> tCase;     while (tCase-- > 0) {         int n;         cin >> n;         cout << dp[n] << endl;     }     return 0; } Colored by Color Scripter

cs

 인덱스가 0부터 시작이기 때문에 DP배열을 dp[12]로 초기화 하여 11인덱스 까지 사용할 수 있도록한다.

 1~3 까지는 값을 미리 넣어두고, 4부터 11까지는 동적계획법으로 각 값을 (dp[i - 1] + dp[i - 2] + dp[i - 3]) 방식으로 채워준다.

처음에는 어떻게 풀어야 할지 생각을 조금 해야하지만 규칙을 찾고나면 화식을 사용하여 간단하게 풀 수 있다.