[또 LIE ?] 6주차 결과

문제

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

9095번: 1, 2, 3 더하기

코드

package DynamicProgramming;

import java.io.*;

public class OneTwoThreePlus {
    static int[] n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        n = new int[12]; // 조건이 n은 양수이며 11보다 작다.

        for (int i = 0; i < T; i++) {
            int value = Integer.parseInt(br.readLine());
            bw.write(dp(value) + "\n");
        }
        bw.flush();
        br.close();
        bw.close();
    }

    static int dp(int x) { // 1,2,3 은 규칙없이 생성되어 값을 지정해준다.
        if (x == 1) {
            return n[x] = 1;
        }
        if (x == 2) {
            return n[x] = 2;
        }
        if (x == 3){
            return n[x] = 4;
        }
        if (n[x] != 0) { // 만약 이미 구한 값이라면 그 값을 바로 반환한다.
            return n[x];
        }
        // 1로 시작할 경우 나머지 경우의 수는 이미 앞의 숫자로 구할 수 있고, 2와 3도 마찬가지로 앞 수에서 값을 찾을 수 있다.
        return n[x] = dp(x - 1) + dp(x - 2) + dp(x - 3);
    }
}

 풀이

└이미 거친 숫자는 바로 숫자를 받아오면 되기 때문에 0이 아닐 때라는 조건을 넣어서 보다 빠른 출력을 할 수 있다.

느낀점

└평소 피보나치 문제를 풀 때 처럼 했으면 많은 시간이 걸렸을 문제이지만, DP를 배운 후로 시간복잡도에 대해 더 자세히 알게 되었다.