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

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

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

---

 

해석 및 팁

 

---

 

이 문제는 백준 9095 1, 2, 3 더하기와 거의 같은 문제입니다. 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] 이므로 다이나믹프로그래밍을 사용하주면 되고  1,000,000,009로 나눈 나머지를 출력해야하므로 모듈러연산을 이용해 주면 됩니다.

 

---

 

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();
   
    for(int i = 0; i < t; i++) {
      int n = sc.nextInt();
      long[] arr = new long[1000001];
      arr[1] = 1;
      arr[2] = 2;
      arr[3] = 4;
      for(int j = 4; j <= n; j++) arr[j] = (arr[j - 1] + arr[j - 2] + arr[j - 3]) % 1000000009;
      sb.append(arr[n]+"\n");
    }

    System.out.println(sb);
  }
}