[백준] 9095번: 1,2,3 더하기 (Java)

1. 문제설명

정수 n이 주어졌을 때, n을 1, 2, 3의 조합으로 나타내는 방법의 수를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 512MB

 

2. 접근 방식

• DP 방법을 사용한다.
• dp[i] 는 i를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 저장한다.
• dp[i] 는 dp[i-1], dp[i-2],dp[i-3] 의 합으로 계산한다.

 

3. 올바른 접근 방식 및 해결 방식

https://lotuslee.tistory.com/43

 

4. 최종 코드

import java.io.*;

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());

        // dp 배열 초기화: dp[i]는 i를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 의미
        int[] dp = new int[12]; // 문제에서 n이 최대 11
        dp[1] = 1; // 1을 만드는 방법은 1가지 (1)
        dp[2] = 2; // 2를 만드는 방법은 2가지 (1+1, 2)
        dp[3] = 4; // 3을 만드는 방법은 4가지 (1+1+1, 1+2, 2+1, 3)

        // DP 배열을 채움: 4부터 11까지의 값을 점화식을 통해 계산
        for(int i=4; i<=11; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}

 

5. 느낀점 or 기억할정보

처음에 단순히 완전탐색 방법으로 해결했었는데, 완전탐색은 중복 계산이 많이 발생하기 때문에 n이 커질수록 시간복잡도가 급격히 증가하게 된다.

DP(동적계획법) 방법을 사용하면 점화식을 통해 배열을 채워 중복 계산이 없고, 시간복잡도 $O(n)$으로 빠르게 원하는 값을 찾을 수 있다.