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

문제 및 입출력

문제 접근

이 문제를 보고 Dynamic Programming을 이용하는 것을 알았다.

4를 나타내는 방법을 모두 나열하면 다음과 같다.

여기서 알 수 있듯이, 4는 3을 나타내는 방법과 2를 나타내는 방법과 1을 나타내는 방법을 모두 더함으로써 가지 수를 구할 수 있었다.

이를 정규화 하면, a-1과 a-2와 a-3의 가지 수를 더하면 a의 가지 수를 구할 수 있다.

구현 코드

import java.io.*;

public class Main {
  static int dp[];

  static int cal(int a){
    if(a == 0 || a == 1) {
      return 1;
    } else if(a == 2) {
      return 2;
    } else if(dp[a] > 0) {
      return dp[a];
    } else {
      dp[a] = cal(a-1) + cal(a-2) + cal(a-3);
      return dp[a];
    }
  }

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

    dp = new int[12];

    for(int i = 0; i < T; i++){
      int n = Integer.parseInt(br.readLine());
      System.out.println(cal(n));
    }
  }
}