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

🔒문제 설명

문제 설명 : 주어진 수를 1, 2, 3을 이용하여 더하는 방법의 수를 구합니다.

ex> 3은 1+1+1 / 2+1 / 1+2 / 3 의 4가지 방법이 있습니다.

input  : 3
		 4
         7
         10
        
output : 7
		 44
         274
         

🔑해결 아이디어

숫자 n의 1,2,3을 이용한 덧셈 방법 수를 구하는 방법의 수를 DP(n)이라고 둔다면,
DP(n)을 구하는 방법은 다음과 같습니다.

n = 1 + (n-1 의 덧셈 방법) = 2 + (n-2 의 덧셈 방법) = 3 + (n-3 의 덧셈 방법)
    => DP(n) = DP(n-1) + DP(n-2) + DP(n-3)

💻소스코드

<소스 코드>

import java.util.*;
public class BJ9095 {
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> DP = new ArrayList<>();
        	//자바 내에서 배열의 크기를 유동적으로 사용하기 위해 ArrayList를 사용
            
        DP.add(1);
        DP.add(2);
        DP.add(4);
      		//1, 2, 3의 경우 DP값을 직접 초기화
            
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();

            if (DP.size() > num) {
                System.out.println(DP.get(num-1));
            }
            	//수행시간을 줄이기 위해 이미 구해져 있는 DP값이 있다면 그 값을 사용
            
            else{
                while(DP.size()<num){
                    int next_step = DP.get(DP.size()-1) + DP.get(DP.size()-2) + DP.get(DP.size()-3);
                    DP.add(next_step);
                }
                System.out.println(DP.get(num-1));
            }
        }
    }
}