[백준] 15989 1,2,3 더하기 4 - Java

 

 

 

문제 출저

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

15989번: 1, 2, 3 더하기 4

 

 

 

문제 풀이

숫자가 주어졌을 때, 1,2,3 을 더하여 숫자를 만들 수 있는 경우의 수를 구해야 합니다.

 

DP를 이용하여 풀었습니다. 점화식을 세우는게 중요합니다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 칩니다. 이 때문에 수식을 오름차순으로 만들었습니다.

 

int[][] dp 2차원 int 배열을 만들었습니다.

dp[i][j] : i는 구해야하는 숫자, j 는 수식의 마지막에 오는 숫자

 

오름차순으로 수식을 만들었기 때문에 j 이하의 수식을 더하면 됩니다.

 

6으로 치면 

 

j = 1인 경우 

6 = 1+1+1+1+1+1  (dp[6][1] = dp[5][1])

 

j = 2인 경우

6 = 1+1+1+1+2

6 = 1+1+2+2

6 = 2+2+2

dp[6][2] = dp[4][1] + dp[4][2]

 

j = 3인 경우

6 = 1+1+1+3

6 = 1+2+3

6 = 3+3 

dp[6][3] = dp[3][1] + dp[3][2] + dp[3][3] = 7

 

int answer = dp[6][1] + dp[6][2] + dp[6][3]

 

점화식을 세우자면 다음과 같습니다.

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]

 

점화식을 통해 문제를 풀었습니다. 

 

 

 

소스 코드

package baekjoon.backjoon10.day2131.day31;


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

/*
1, 2, 3 더하기 4
https://www.acmicpc.net/problem/15989
 */
public class B15989 {

  static int t;
  static int n;
  static int[][] dp;

  static StringBuilder sb;

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

    t = Integer.parseInt(br.readLine());
    sb = new StringBuilder();

    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;

    /*
     오름차순으로 수식 정리

     5로 예를 들면
     수식이 1로 끝나려면 앞에는 다 1이어야 함. 오름차순으로 수식을 정리했으니까
     1+1+1+1+1

     수식이 2로 끝나려면 앞에는 1,2 이여야 함
     1+1+1+2
     1+2+2

     수식이 3으로 끝나려면 앞에는 1,2,3 이여야함
     1+1+3
     2+3

    */
    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];
    }

    for(int i = 0; i < t; i++) {
      n = Integer.parseInt(br.readLine());
      simulation();
    }

    System.out.println(sb.toString());

    System.out.println(dp[6][1] + dp[6][2] + dp[6][3]);

  }

  public static void simulation() {
    int answer = dp[n][1] + dp[n][2] + dp[n][3];
    sb.append(answer).append("\n");
  }

}