[15989/Java] 1,2,3 더하기 4

문제

---

입력 및 출력

---

풀이

import java.util.*;
import java.io.*;
class Main {  
  static int[][] dp;
  static int T,input, result;
  public static void main(String args[]) throws Exception { 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 테스트케이스
    T = Integer.parseInt(br.readLine());

    // 결과 값을 담을 StringBuilder
    StringBuilder sb = new StringBuilder();

    // T만큼 반복문 수행
    for(int i=0; i<T; i++){
      input = Integer.parseInt(br.readLine());

      // DP 메서드 호출
      DP();

      sb.append(result).append("\n");
    }

    System.out.println(sb);
  }
  public static void DP(){
    // dp객체 초기화
    dp = new int[10001][4];

    // 기본 1,2,3의 케이스 설정
    dp[1][1] = dp[2][2] = dp[3][3] = 1;

    // input 값이 4이상 인 경우
    if(input>=4){
      for(int i =1; i<=input; i++){
        for(int j=1; j<=3; j++){
          if(i > j){
            for(int k=1; k<=j; k++){
              dp[i][j]+=dp[i-j][k];
            }
          }
        }
      }
      // result 값 초기화
      result = 0;
      for(int i=1; i<=3; i++){
        result += dp[input][i];
      }
    }
    //input 값이 3이하인 경우
    else{
      result = input;
    }    
  }
}

---

결과 및 해결방안

[결과]

[해결방안]

위와 같이 나열하여 발견한 규칙을 활용해서 풀이

결과값 : [n][1] + [n][2] + [n][3]
점화식 :
[n][1] = [n-1][1]
[n][2] = [n-2][1] + [n-2][2]
[n][3] = [n-3][1] + [n-3][2] + [n-3][3]