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

문제보기

1. 다이나믹으로 풀기

import java.io.*;
import java.util.*;

public class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.valueOf(bf.readLine());
    // N은 최대 11이므로
    int[] d = new int[12];
    d[1] = 1;
    d[2] = 2;
    d[3] = 4;
    
    // 1,2,3 의 합으로 나타내는 경우의 수 구하기
    // 예를들어 d[4] = d[3]( 3+1 = 4) + d[2]( 2+2 = 4 ) + d[1]( 1+3 = 4)
    for(int i = 4 ; i <= 11 ; i++ ){
      d[i] = d[i-1] + d[i-2] + d[i-3];
    }
    
    
    StringBuilder sb = new StringBuilder();
    while(n-- > 0){
      sb.append(d[Integer.valueOf(bf.readLine())]);
      sb.append("\n");
    }
    System.out.println(sb);
  }
}

1. 재귀로 풀기

import java.util.*;

public class Main {
  public static int go(int sum, int goal){

    //목표값보다 합이 넘어가는 경우는 필요읎다
    if(sum > goal) return 0;
    //목표값과 합이 같다면 cnt++되어야함 
    if(sum == goal) return 1;
    
    int now = 0;
    // 1, 2, 3을 넣는 경우를 각각 재귀호출
    // 목표값과 일치한다면 1이 반환되므로 now에 차곡차곡 값이 쌓일것..
    for(int i = 1; i <= 3; i++){
      now += go(sum+i, goal);
    }
    return now;
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();

    while(t-- > 0){
      int goal = sc.nextInt();
      int cnt = go(0, goal);
      System.out.println(cnt);
    }       
  }
}

N이 작기 때문에 그냥 떠오르는대로 빠르게 푸는것이 중요