Java 9095 1, 2, 3 더하기

풀이 :

우선 해당문제의 설명부분에서 4의 경우의 수는 총 7가지가 되는 것을 보여주는 거처럼, n의 경우의 수는 (n-1) + (n-2) + (n-3)으로 구할 수 있습니다.

그래서 int형 배열을 생성해주고 n은 11보다 작으니 10까지의 경우의 수를 배열에 저장해준 뒤 입력 받은 값을 출력하는 되는 문제입니다.

이렇게 반복된 연산을 효율적으로 풀어주는 것을 동적 프로그래밍, 다이나믹 프로그래밍 다른 말로는 기억하기 프로그래밍이라고도 합니다.

앞으로는 자료구조와 동적 프로그래밍 문제를 많이 풀어볼 예정입니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int cnt = Integer.parseInt(br.readLine());
        
        int[] dp = new int[11];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for(int i = 4; i < 11; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        for(int i = 0; i < cnt; i++){
            int num = Integer.parseInt(br.readLine());
            sb.append(dp[num]).append("\n");
        }
        System.out.println(sb);
        
        br.close();
        
        
    }
}