BOJ - 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

• DP 기본 문제이다.
  • 메모리제이션으로 각 DP마다 결과 값을 저장하여 사용해야 시간초과가 나지않는다.
  • 코딩테스트 몸 풀기용으로 간혹 나오는 경우가 있다. 

 

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws Exception {

        int T = scanner.nextInt();

        while (T-- > 0) {
            int target = scanner.nextInt();
            System.out.println(dp(target));
        }
    }

    private static int dp(int target) {
        int[] memo = new int[target + 3];
        memo[1] = 1;
        memo[2] = 2;
        memo[3] = 4;
        if (target < 4) {
            return memo[target];
        }

        for (int i = 4; i <= target; i++) {
            memo[i] = memo[i - 3] + memo[i - 2] + memo[i - 1];
        }
        return memo[target];
    }
}