백준

백준 9095 1, 2, 3 더하기(Java)

Park DJ 2023. 1. 30. 16:08

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

 

9095번: 1, 2, 3 더하기

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

www.acmicpc.net


 

해석 및 팁

 


 

이 문제는 다이내믹프로그래밍으로 풀면 되는 문제입니다. arr [1] = 1, arr [2] = 1+1, 2, arr [3]= 1+1+1, 1+2, 2+1, 3 일 때 arr [4]부터는 arr [n] = arr [n-1] + arr [n-2] + arr [n-3] 이므로 빈복문을 통해 arr [n]의 값을 구해주면 됩니다.

 


 

Java 코드

 


import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int t = sc.nextInt();
    int[] arr = new int[12];
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;
    
    for(int i = 0; i < t; i++) {
      int n = sc.nextInt();
      for(int j = 4; j <= n; j++) {
        arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3];
      }
      sb.append(arr[n]+"\n");
    }
    
    System.out.println(sb);
  }
}