[BOJ/Java] 9095. 1, 2, 3 더하기

[BOJ/Java] 9095. 1, 2, 3 더하기

9095번: 1, 2, 3 더하기

---

문제 해석

이 문제에서는 주어진 정수 𝑛n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 동적 프로그래밍(Dynamic Programming) 문제이다. 예를 들어, 𝑛=4n=4인 경우, 다음과 같이 총 7가지 방법이 있다:

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

풀이 과정

이 문제의 풀이는 각 숫자를 1, 2, 3의 합으로 나타내는 방법의 수를 배열 dp에 저장하는 것을 포함한다. 여기서 dp[i]는 숫자 𝑖i를 나타내는 방법의 수를 저장한다. 초기 값으로 dp[1] = 1, dp[2] = 2, dp[3] = 4를 설정하고, 4 이상의 모든 숫자에 대해 다음의 점화식을 적용한다:

𝑑𝑝[𝑖]=𝑑𝑝[𝑖−1]+𝑑𝑝[𝑖−2]+𝑑𝑝[𝑖−3] 

이 점화식은 𝑖를 나타내기 위해 마지막에 1, 2, 또는 3을 더하는 경우를 고려하여 계산된다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No9095;

import java.io.*;

public class Main {
    private static int T; // 테스트 케이스 수
    private static int[] dp = new int[11]; // dp 배열

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

        sol(); // dp 배열을 채우는 메소드 호출

        T = Integer.parseInt(br.readLine()); // 테스트 케이스 수 읽기
        for (int t = 0; t < T; t++) {
            sb.append(dp[Integer.parseInt(br.readLine())]).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sol() {
        dp[1] = 1; dp[2] = 2; dp[3] = 4; // 초기 조건 설정
        for(int i = 4; i < dp.length; i++) { // 4부터 10까지의 모든 수에 대해
            for (int j = i-3; j < i; j++) {
                dp[i] += dp[j]; // dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
            }
        }
    }
}

시간 복잡도 분석

sol 함수에서 dp 배열을 채우는데 각 숫자 𝑖i에 대해 세 개의 이전 숫자의 값을 읽고, 이는 𝑂(1)의 연산을 세 번 반복하는 것이므로 𝑂(𝑛)의 시간 복잡도를 가진다. 여기서 𝑛은 dp 배열의 크기이다.

느낀점

이 문제를 통해 동적 프로그래밍의 기초를 다지는 좋은 기회가 되었다. dp 배열을 활용하여 점화식을 적용하는 방법을 연습할 수 있었고, 간결한 접근 방식으로 문제를 해결하는 법을 배울 수 있었다. 동적 프로그래밍 문제를 풀 때 기본적인 접근 방식을 어떻게 확장하고 응용할 수 있는지에 대한 더 깊은 이해를 얻었다.