[백준 JAVA] 9095 1, 2, 3 더하기

9095 1, 2, 3 더하기

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

문제설명

주어진 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구한다.

접근방식

O(I^2)  시간복잡도

 

dp 배열을 최대 n까지 계산하고, 각 테스트케이스에 대해 조회하는 시간은 상수 시간이 소요된다. 

 

문제 조건 분석 과정

 

dp[i]를 정의하여 i를 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 저장한다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] (단, i-1, i-2, i-3이 유효한 범위일 때)

전체코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        // 각 테스트 케이스에서 입력될 값을 저장할 배열
        int[] queries = new int[T];
        int max_n = 0;

        // 입력된 각 테스트 케이스의 값을 배열에 저장하고, 최대 값을 찾는다
        for (int i = 0; i < T; i++) {
            queries[i] = Integer.parseInt(br.readLine());
            if (queries[i] > max_n) {
                max_n = queries[i];
            }
        }

        // max_n까지의 값을 위한 dp 배열
        // dp[i] = i를 1, 2, 3의 합의 경우의 수
        int[] dp = new int[max_n + 1];
        dp[0] = 1; // 0을 만드는 방법은 1가지 (빈 집합)

        for (int i = 1; i <= max_n; i++) {
            // dp[i - 1]을 더한다.
            dp[i] += (i - 1 >= 0) ? dp[i - 1] : 0;
            // dp[i - 2]를 더한다.
            dp[i] += (i - 2 >= 0) ? dp[i - 2] : 0;
            // dp[i - 3]을 더한다.
            dp[i] += (i - 3 >= 0) ? dp[i - 3] : 0;
        }

        StringBuilder sb = new StringBuilder();
        for (int n : queries) {
            // 각 쿼리에 대해 dp[n] 저장
            sb.append(dp[n]).append("\n");
        }

        System.out.print(sb.toString());
    }
}