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

+ Recent posts