728x90
https://www.acmicpc.net/problem/15989
15989번: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
// 코드
|
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
38
39
40
|
import java.util.*;
import java.io.*;
public class Main {
// main
public static void main(String[] args) throws Exception{
// Please Enter Your Code Here
StringBuilder sb = new StringBuilder();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][] dp = new int[10001][4];
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;
for ( int i = 4; i < 10001; ++i ) {
dp[i][1] = dp[i - 1][1];
dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
}
int T = Integer.parseInt(br.readLine());
while ( T --> 0 ) {
int n = Integer.parseInt(br.readLine());
sb.append((dp[n][1] + dp[n][2] + dp[n][3])).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
|
cs |
반응형