[BOJ] 15988 1,2,3 더하기 3 - JAVA

1. 문제

15988번: 1, 2, 3 더하기 3

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

2. 풀이

숫자 N을 1,2,3의 합으로 나타내는 방법은 N-1에 1을 더한 것, N-2에 2를 더한 것, N-3에 3을 더한 것을 모두 더하면 알 수 있다.

dp[1] = 1 

dp[2] = 2 (1+1, 2)

dp[3] = 4 (1+1+1, 2+1, 1+2, 3)

이 걸 기본 값으로 두고 100만개까지 dp를 모두 완성해둔다.

테스트케이스를 저장하고, N을 입력받을 때마다 dp값을 sb에 더한다.

import java.io.*;

public class BOJ_15988_123더하기3 {
   public static void main(String[] args) throws IOException {
      int MOD = 1_000_000_009;
      int[] dp = new int[1000001];
      dp[1] = 1;
      dp[2] = 2;
      dp[3] = 4;
      for(int i=4;i<1000001;i++) dp[i] = ((dp[i-1] + dp[i-2])%MOD + dp[i-3])%MOD;

      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      for(int tc=0;tc<T;tc++){
         sb.append(dp[Integer.parseInt(in.readLine())]).append('\n');
      }
      
      System.out.print(sb);
   }
}

---

3. 결과