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

목차

• 문제풀이
• 제출코드

 

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

 

 

문제풀이

시간제한이 1초이므로 일반적인 for문은 사용할 수 없다. DP로 풀어보겠다.

정수 n은 양수이며 11보다 작다. 1, 2, 3의 합으로 나타내야한다.

[0]~[10]인 배열을 생성했다고하자. [0]은 사용하지 않는다. 

 

잘 살펴보면

[2]는 [1]에 +1을 더한값과 자기자신인 2를 가지고 있고

[3]은 [2]에 +1을 더한값과 자기자신인 3을 가지고 있다.

[4]는 [3]+1, [2]+2, [1]+3을 더한값을 가지고있지만 자기자신인 "4"는 표현할 수 없기 때문에 제외되었다.

[5]는 [4]+1, [3]+2, [2]+3, [1]+4로 표현할 수 있지만 "4"는 구성요소인 1, 2, 3이 아니기때문에 제외되었다.

 

 

제출코드

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

public class Main {

    static int[] nums = new int[11];

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

        //배열 값 셋팅
        for (int i = 4; i <= 10; i++) {
             nums[i] = nums[i-3] + nums[i-2] + nums[i-1];
        }

        //출력
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(nums[n]);
        }
    }

}