1, 2, 3 더하기 백준 9095 ( dp )

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

 

dp를 활용한 문제.

처음에는 덧셈 결과를 가지고 점화식을 세우는줄 알았는데,
합이 1일때 경우의수

합이 2일때 경우의수

합이 3일때 경우의수 ,,,, 이렇게 해서 

dp[i] = dp[i-3]+dp[i-2]+dp[i-3] 점화식을 세워서

for 루프를 한번만 돌려서 O(N) 시간 복잡도가 걸린다.

 

악필이지만 이해바람

 

이렇게 규칙을 발견하면 i-1, i-2, i-3 더한 값이 i 에 할당되는 점화식을 세울 수 있다.

 

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

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

 

그래서 코드에서도 보듯이 첫 값을

dp[1] : 합이 1일때 경우의 수

dp[2] : 합이 2일때 경우의 수

dp[3] : 합이 3일때 경우의 수

할당시켜놓고 4부터 for 반복문을 돌면서 dynamic programming을 해주면 답이 나온다.

끝.