[백준] 15990 1, 2, 3 더하기 5 - Java

 

 

 

문제 출저

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

15990번: 1, 2, 3 더하기 5

 

 

 

문제 풀이

테스트 케이스 t가 주어집니다. t의 수 만큼 n이 주어질 때, 1,2,3을 더해서 n을 만들 경우의 수를 구해야 합니다. 이 때 연속으로 같은 수가 오면 안됩니다. 경우의 수에 1_000_000_009의 나머지 값을 구해야 합니다. 

 

dp로 문제를 풀었습니다.

n의 범위는 100_000 입니다. dp[100_001][4] 2차원 배열을 만들었습니다.

dp[n][1] 이것은 n번째 수의 1로 끝나는 경우의 수 입니다. 

n의 모든 경우의 수는 dp[n][1] + dp[n][2] + dp[n][3] 입니다. 

dp 탐색 과정과 정답을 더하는 과정에 1_000_000_009를 나누어 정답을 구했습니다. 

 

 

 

소스 풀이

package baekjoon.backjoon11.day1120.day11;

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

/*
1, 2, 3 더하기 5
https://www.acmicpc.net/problem/15990
 */
public class B15990 {

  static int t;
  static int n;
  static long[][] dp;
  static long inf = 1_000_000_009;

  public static void main(String[] args) throws IOException {
    dp = new long[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_001; i++) {
      dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % inf;
      dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % inf;
      dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % inf;
    }

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    t = Integer.parseInt(br.readLine());

    StringBuilder sb = new StringBuilder();

    for(int i = 0; i < t; i++) {
      n = Integer.parseInt(br.readLine());
      long answer = (dp[n][1] + dp[n][2] + dp[n][3]) % inf;
      sb.append(answer).append("\n");
    }

    System.out.println(sb);

  }

}