https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
정수를 1, 2, 3의 합으로만 나타내는 방법의 수를 출력하는 dp문제입니다.
1 → 1 (1개)
2 → 1+1, 2 (2개)
3 → 1+1+1, 1+2, 2+1, 3 (4개)
4 → 1+1+1+1, 1+1+2, 1+2+1, 1+3 / 2+1+1, 2+2 / 3+1 (7개)
여기서 4는
3을 나타내는 방법에 1을 더한것과
2를 나타내는 방법에 2를 더한것과
1을 나타내는 방법에 3을 더한것을
모두 더한 값이 되는것을 알 수 있습니다.
이것으로 점화식을 나타내면 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]이 됩니다.
(+Java 소스 추가하였습니다.)
[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
25
26
27
|
#include <iostream>
using namespace std;
int N, dp[11];
void init() {
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= 10; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
}
int main() {
init();
int Testcase;
cin >> Testcase;
while (Testcase--) {
cin >> N;
cout << dp[N] << '\n';
}
return 0;
}
|
cs |
[Java]
|
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
28
29
30
31
32
33
34
35
36
37
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int dp[] = new int[11];
static int N;
static void init() {
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= 10; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws Exception {
init();
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
sb.append(dp[N] + "\n");
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 15988 1, 2, 3 더하기 3 (0) | 2021.01.22 |
|---|---|
| boj 12101 1, 2, 3 더하기 2 (0) | 2021.01.22 |
| boj 14226 이모티콘 (0) | 2021.01.22 |
| boj 17070 파이프 옮기기 1 (0) | 2021.01.22 |
| boj 11053 가장 긴 증가하는 부분 수열 (0) | 2021.01.22 |