[BOJ/DP] 백준 9095 - 1, 2, 3 더하기 / 15988 - 1, 2, 3 더하기 3 / 15990 - 1, 2, 3 더하기 5 (Java)

9095 - 1, 2, 3 더하기

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

문제

정수 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의 합으로 나타내는 방법의 수

입력
첫째 줄: 테스트 케이스 개수 T
0 < 정수 n < 11
출력
각 테스트 케이스마다 n을 1, 2, 3의 합으로 나타내는 방법의 수

---

풀이

• `dp[i]`: 정수 i를 1, 2, 3의 합으로 만드는 경우의 수
• `dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]` => 예시 참고

 

• dp[1] = 1 
  • 1
• dp[2] = 2 
  • 1 + 1 / 2
• dp[3] = 4
  • 1 + 1 + 1 / 1 + 2 / 2 + 1 / 3

---

예시

• n = 2
  • 1 + 1
  • 2
• n = 3
  • 1 + 1 + 1
  • 1 + 2
  • 2 + 1
  • 3
• n = 4
  • 1 + 1 + 1 + 1
  • 1 + 1 + 2
  • 1 + 2 + 1
  • 2 + 1 + 1
  • 2 + 2
  • 1 + 3
  • 3 + 1
• n = 5
  • 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 2
  • 1 + 1 + 2 + 1
  • 1 + 2 + 1 + 1
  • 2 + 1 + 1 + 1
  • 2 + 2 + 1
  • 1 + 3 + 1
  • 3 + 1 + 1
  • 1 + 1 + 3
  • 2 + 1 + 2
  • 1 + 2 + 2
  • 3 + 2
  • 2 + 3

=> dp[5] = dp[4] + dp[3] + dp[2]

• 4를 만드는 방법 + 1 
• 3을 만드는 방법 + 2 
• 2를 만드는 방법 + 3

=> 7 + 4 + 2 = 13

---

코드

import java.io.*;

public class boj_9095 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());

        int[] dp = new int[11];
        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];
        }

        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}

---

15988 - 1, 2, 3 더하기 3

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

문제

정수 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의 합으로 나타내는 방법의 수

입력
첫째 줄: 테스트 케이스 개수 T
0 < 정수 n <= 1,000,000
출력
각 테스트 케이스마다 n을 1, 2, 3의 합으로 나타내는 방법의 수 % 1,000,000,009

---

풀이

• `dp[i]`: 정수 i를 1, 2, 3의 합으로 만드는 경우의 수
• `dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]` => 예시 참고

 

• dp[1] = 1 
  • 1
• dp[2] = 2 
  • 1 + 1 / 2
• dp[3] = 4
  • 1 + 1 + 1 / 1 + 2 / 2 + 1 / 3

 

주의:` long[] dp = new long[1_000_000];`

=> `int` 범위 초과할 수 있기 때문에 `long`

---

코드

import java.io.*;

// 1, 2, 3 더하기 3
public class boj_15988 {
    static final int MOD = 1_000_000_009;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        long[] dp = new long[1_000_001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i < 1_000_001; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
        }

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }

        System.out.print(sb);
    }
}

---

15990 - 1, 2, 3 더하기 5

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

문제

정수 4 -> 1, 2, 3의 합으로 나타내는 방법: 3가지 
(합을 나타낼 때는 수 1개 이상 사용)
1 + 2 + 1
1 + 3
3 + 1

=> 정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는 방법의 수

입력
첫째 줄: 테스트 케이스 개수 T
0 < 정수 n <= 1,000,000
출력
각 테스트 케이스마다 n을 1, 2, 3의 합으로 나타내는 방법의 수 % 1,000,000,009

---

풀이

• 같은 수가 연속해서 2번 X
  • 1 + 2 + 1 (O) / 1 + 1 + 2 (X)
• `dp[i][j]`: i를 만들 때, 마지막에 사용한 수가 j인 경우의 수
  • j = 1, 2, 3 중 하나
  • ex. `dp[1][1] = 1`: 정수 1을 만드는 경우의 수 중 마지막에 1을 쓴 경우 1가지
• `dp[i][j] = dp[i - j][k]` (`k != j`)
  • 현재 수를 제외한 다른 수로 끝나는 경우 + j
  • ex. `dp[i][2] = dp[i - 2][1] + dp[i - 2][3])`
    • i를 만들 때 마지막에 2를 쓴 경우 -> 이전 숫자가 2가 아니여야 함 => 1, 3만 가능
    • 2를 썼기 때문에 2만큼 줄여야 함

 

• 마지막 수가 1, 2, 3일 경우의 수 

for (int i = 4; i <= 100_000; i++) {
    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
}

 

• 모듈러 연산
  • `dp[N][1] + dp[N][2] + dp[N][3]) % MOD`
  • -> `((dp[N][1] + dp[N][2]) % MOD + dp[N][3]) % MOD`

=> 오버플로우 방지

---

코드

import java.io.*;

// 1, 2, 3 더하기 5
public class boj_15990 {
    static final int MOD = 1_000_000_009;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        int[][] dp = new int[100_001][4];
        dp[1][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;

        for (int i = 4; i <= 100_000; i++) {
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
        }

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int res = ((dp[N][1] + dp[N][2]) % MOD + dp[N][3]) % MOD;
            sb.append(res).append("\n");
        }

        System.out.println(sb);
    }
}