0%

[백준/9095] 1, 2, 3 더하기

작성일 Edited on In Disqus:

Baekjoon Online Judge - 9095

Review

  • 각 앞자리 수에 1,2,3이 나올 경우를 생각하면 된다. 예를 들어 숫자 4는 3을 만들었을 때의 경우의 수, 2를 만들었을 때의 경우의 수, 1을 만들었을 때의 경우의 수를 전부 추가하면 된다.
    example
  • 점화식으로 나타내면 이렇다. A[n] = A[n-3] + A[n-2] + A[n-1]

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int[] arr = new int[11];
    int T, n;

    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;

    T = sc.nextInt();

    for(int i = 0; i < T; i++) {
      n = sc.nextInt();
      for(int j = 4; j<=n; j++) {
        arr[j] = arr[j-1] + arr[j-2] + arr[j-3];
      }
      System.out.println(arr[n]);
    }
    sc.close();
  }
}