문제 접근

문제를 보고 어디선가 본 문제 같았고 dp라는 것은 생각보다 쉽게 떠올릴 수 있었다. 처음에는 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 의 점화식에서 중복된 값들만 제거하면 될거라고 생각했다. 그런데, 생각보다 중복된 값을 제거하는 규칙이 찾아지지 않았다. 여기서 중복을 제거하는 방법을 찾으려고 거의 한 시간을 넘게 투자했지만 못찾았고 뭔가 잘못됐음을 깨달았다. 곰곰히 생각해본 결과, 점화식을 분리하기로 했다.

dp1: 1 로만 N을 만들기 -> 이 경우의 수는 모든 경우가 1이다.
dp2: 1,2로만 N을 만들기 -> 이 경우의 수는 N/2+1 이다.
dp3: 1,2,3으로만 N을 만들기 -> 시그마 k=(0~N/3)에 대해, dp2[N-3K]의 합이다.

그렇다면, 시간 복잡도는 어떻게 될까?
dp2를 이 문제의 범위인 10000까지 한 번에 구해놓는게 시간상 좋다.
dp2를 구하는데 10000번의 연산, O(N)
문제 N이 주어졌을때, dp3[N]을 구하는데 O(N/3 + 1) -> O(N)의 시간이 걸린다.

따라서, 어떤 숫자 N이 주어졌을때 답을 구하는데 O(N)의 시간에 해결이 가능하다.

문제 풀이

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

class Main {
    static int T;

    static public void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        int[] dp2 = new int[10001];
        dp2[0] = 1;
        for (int i = 1; i < 10001; i++) {
            dp2[i] = i / 2 + 1;
        }

        StringBuilder sb = new StringBuilder();
        int N = 0;
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            int result = 0;
            for (int k = 0; k <= N / 3; k++) {
                result += dp2[N - 3 * k];
            }
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

여담

어제 교내 알고리즘 대회에서 팀원들과 동상을 수상해서 기분이 매우 좋다. 운이 좋았던 것은, 특정된 알고리즘이 요구되는 문제보다는 수학 문제 느낌의 구현 위주 문제들이 나와서 우리 팀이 힘을 낼 수 있었던 것 같다. 이 팀 그대로 ICPC까지 의미있는 결과를 얻기 위해 다시 알고리즘을 풀고있다.