Data Structure - Algorithm/Baekjoon

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

Alex Han 2025. 2. 25. 00:09
반응형

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

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

예제 입력

3
4
7
10

 

예제 출력

7
44
274

 

해결 코드

import java.util.Scanner;

public class Main {
    static int[] dp = new int[12];

    static public int oneTwoThree(int n) {
        // 초기 조건
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        // 점화식
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt();
            System.out.println(oneTwoThree(n));
        }
    }
}

 

 

 

이 문제는 동적 프로그래밍(Dynamic Programming) 기법을 사용하면 효율적으로 해결할 수 있다.

 

1. 문제를 해결하는 방법: 점화식 도출

• 숫자를 1, 2, 3의 합으로 나타내는 모든 경우의 수를 구해야 한다.

• 특정 숫자를 만들기 위해 그 숫자에서 1, 2, 3을 뺀 나머지 수에서 도달할 수 있는 방법의 수를 더하면 된다.

 

점화식 유도

• n을 1, 2, 3의 합으로 나타내는 경우는 다음 세 가지 경우로 나뉜다:

 

1. 마지막에 1을 더한 경우 → n-1까지의 방법에 1을 추가

2. 마지막에 2를 더한 경우 → n-2까지의 방법에 2를 추가

3. 마지막에 3을 더한 경우 → n-3까지의 방법에 3을 추가

 

• 이를 점화식으로 표현하면 다음과 같다:

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

 

2. 초기 조건 설정

작은 수부터 규칙을 찾아보면:

 

• dp[1] = 1 → (1)

• dp[2] = 2 → (1+1, 2)

• dp[3] = 4 → (1+1+1, 1+2, 2+1, 3)

 

따라서:

dp[1] = 1  
dp[2] = 2  
dp[3] = 4

 

 

 

3. 점화식 적용 및 DP 사용 이유

• 점화식을 재귀적으로 계산하면 중복 계산이 발생하므로, 동적 프로그래밍을 사용해 계산된 값을 저장하고 재사용한다.

• 이를 통해 중복 연산을 방지하고 효율적으로 값을 구할 수 있다.

 

 

 

4. 시간 및 공간 복잡도 분석

 

• 시간 복잡도: O(n)

• 1부터 n까지 한 번씩 순회하면서 점화식을 적용하므로 선형 시간 복잡도.

• 공간 복잡도: O(n)

• dp[] 배열에 최대 n개의 값을 저장하므로 선형 공간 복잡도.

 

 

 

5. 정리 및 결론

• 이 문제는 부분 문제로 나누어 해결할 수 있으며, 이전에 계산한 결과를 재사용할 수 있기 때문에 동적 프로그래밍이 적합하다.

• 점화식을 도출하고, DP 배열에 저장하면서 재사용하는 방식으로 중복 연산을 제거하여 시간 복잡도를 줄였다.

• 이러한 방식은 동적 프로그래밍의 대표적인 적용 예시 중 하나이다.

반응형