[백준] 123더하기 4 15989 java

최적의 풀이는 아니지만 문제 접근하는 방법이 참고가 될 수 있지 않을까해서 올려봅니다. 코드에 주석 참고해주세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class $123더하기4_15989_2 {
  // 순서 상관없이 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수
  // dp 문제
  // 점화식 세우는 게 어려웠다.
  // 정수 n은 3가지의 경우로 나눌 수 있다.
  // 첫째, 1로만 구성되어져 있는 경우
  // 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 예를 들어 정수 3의 경우에는
  // 1 + 1 + 1 : 첫째, 1로만 구성되어져 있는 경우
  // 2 + 1     : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 3         : 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 정수 4의 경우에는
  // 1 + 1 + 1 + 1 : 첫째, 1로만 구성되어져 있는 경우
  // 2 + 1 + 1     : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 2 + 2         : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 3 + 1         : 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 5의 경우에는
  // 1 + 1 + 1 + 1 + 1 : 첫째, 1로만 구성되어져 있는 경우
  // 2 + 1 + 1 + 1     : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 2 + 2 + 1         : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 3 + 1 + 1         : 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 3 + 2             : 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 6의 경우
  // 1 + 1 + 1 + 1 + 1 + 1 : 첫째, 1로만 구성되어져 있는 경우
  // 2 + 1 + 1 + 1 + 1     : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 2 + 2 + 1 + 1         : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 2 + 2 + 2             : 둘째, 2가 적어도 하나 포함되고 1, 2로만 구성되어져 있는 경우
  // 3 + 1 + 1 + 1         : 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 3 + 2 + 1             : 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 3 + 3                 : 셋째, 3이 적어도 하나 포함되고, 1, 2, 3으로 구성되어져 있는 경우
  // 6을 예를 들어 규칙을 찾아보면 첫째 1로만 구성되어져 있는 경우는 무조건 1가지의 경우의 수가 있고
  // 둘째 2가 적어도 하나 포함되고 1, 2로만 구성되는 경우는 4(6 - 2)의 첫째, 둘째의 경우의 수(3)와 동일하다.
  // 셋째 3가 적어도 하나 포함되고 1, 2, 3으로 구성되되는 경우는 3(6 - 3)의 첫째, 둘째, 셋째 경우의 수(3)와 동일하다.
  // 따라서 6을 1, 2, 3의 합으로 구성하는 경우의 수는 총 1 + 3 + 3 = 7가지이다.
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int t = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < t; i++) {
      sb.append(solve(br)).append("\n");
    }

    System.out.println(sb);
  }

  private static int solve(BufferedReader br) throws IOException {
    int n = Integer.parseInt(br.readLine());
    int[][] dp = new int[Math.max(n + 1, 4)][4];
    dp[1][1] = 1; // 1
    dp[2][1] = 1; // 1 + 1
    dp[2][2] = 1; // 2
    dp[3][1] = 1; // 1 + 1 + 1
    dp[3][2] = 1; // 2 + 1
    dp[3][3] = 1; // 3
    
    for (int i = 4; i <= n; i++) {
      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];
    }

    return Arrays.stream(dp[n]).sum();
  }
}