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

9095_1, 2, 3 더하기

 

링크

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

 

풀이

 

정수 n을 1, 2, 3의 조합으로 나타내는 방법을 찾아야 합니다.

그 방법은 n-1까지의 조합 + 1과 n-2까지의 조합 + 2와 n-3까지의 조합 + 3이 있을 것입니다.

 

4를 1, 2, 3의 조합으로 나타내는 방법을 위를 통해 구해보면,

 

n-1까지의 조합 -> 3까지의 조합

1 + 1 + 1    + 1

1 + 2        + 1

2 + 1        + 1

3            + 1

 

n-2까지의 조합 -> 2까지의 조합

1 + 1    + 2

2        + 2

 

n-3까지의 조합 -> 1까지의 조합

1     + 3

 

이렇게 7가지가 됩니다.

 

점화식을 세워보면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]   (n >= 4)   이 됩니다.

 

DP[1], DP[2], DP[3]은 미리 구해 놓아야 합니다.

아까 위에서 해봤기 때문에 쉽게 구할 수 있습니다.

DP[1] = 1, DP[2] = 2, DP[3] = 4 입니다.

 

코드로 구현하겠습니다. 주의할 점은 n은 11보다 작은 양수, 10 이하의 양수이기 때문에 배열은 11로 잡아야 합니다.

 

 

코드

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

//9095_1, 2, 3 더하기 #include <iostream> using namespace std;   int DP[11] = { 0, 1, 2, 4 };   int f(int n) {     if (DP[n]) return DP[n];     return DP[n] = f(n - 1) + f(n - 2) + f(n - 3); }   int main() {     int T;     int n;     int i;       f(10);            //10까지 미리 구해서 배열에 넣어둠       cin >> T;       for (i = 0; i < T; ++i) {         cin >> n;         cout << DP[n] << endl;     }       return 0; } Colored by Color Scripter

cs