문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
문제접근법.
규칙을 발견해야 문제를 해결할 수 있다. 점화식만 보고 직관적으로 이해가 되면 좋겠지만, 대부분이 그렇지 않을 것이다. n = 4 라는 예제를 통해서 이해도를 높여보자.
n >= 4 일 때,
f(n) = f(n - 1) + f(n - 2) + f(n - 3)이다.
n = 1 일 때, 1
n = 2 일 때, 1 + 1 / 2
n = 3 일 때, 1 + 1 + 1 / 2 + 1 / 1 + 2 / 3
n = 4 일 때, 1 + 1 + 1 + 1 / 1 + 1 + 2 / 1 + 2 + 1 / 2 + 1 + 1 / 3 + 1 / 3 + 1
과 같다,
n = 1일 때, 3을 붙이고 n = 2일 때, 2를 붙이고, n = 3일 때 1을 붙이면 n = 4 일 때 조합을 만들 수 있다.
해설코드(C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[11];
int N, num;
int result = 1;
int main(void) {
//freopen("input.txt", "r", stdin);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= 11; i++) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}
cin >> N;
for (int i = 0; i < N; i++) {
cin >> num;
cout << dp[num] << endl;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘 > 백준' 카테고리의 다른 글
[16234번] 인구 이동(삼성 코딩테스트 SW) (0) | 2019.10.05 |
---|---|
[1463번] 1로 만들기 (0) | 2019.10.05 |
[11722번] 가장 긴 감소하는 부분 수열(DP) (0) | 2019.10.04 |
[11722번] 가장 긴 감소하는 부분 수열 (0) | 2019.10.03 |
[17144번] 미세먼지 안녕! (C++, 삼성코딩테스트) (0) | 2019.10.03 |