백준 9095번 "1, 2, 3 더하기" --- 파이썬

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

백준 9095번 문제인 '1, 2, 3 더하기'는 프로그래밍을 배우는 많은 사람들에게 인기 있는 문제입니다. 이 문제는 주어진 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 것입니다. 이 글에서는 문제를 해결하기 위한 접근 방법과 다이나믹 프로그래밍(DP)을 활용한 코드 구현에 대해 자세히 알아보겠습니다.

문제의 핵심은 주어진 정수 n을 어떻게 1, 2, 3의 조합으로 표현할 수 있는지를 찾는 것입니다. 예를 들어 n이 4일 경우, 가능한 조합은 다음과 같습니다:

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

총 7가지 방법이 있습니다.

이러한 방식으로 n에 대한 모든 조합을 찾아야 하며, 이를 위해 다이나믹 프로그래밍 기법을 사용할 수 있습니다.

문제 해결을 위한 접근 방법:
이 문제를 해결하기 위해서는 각 숫자(n)에 대해 이전 숫자들(n-1, n-2, n-3)의 결과를 활용해야 합니다. 이는 다음과 같은 점화식으로 표현할 수 있습니다:

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

여기서 dp[i]는 i를 만들기 위한 경우의 수입니다. 초기값은 다음과 같이 설정합니다:

dp[1] = 1 (단 하나의 경우: [1])
dp[2] = 2 (두 가지 경우: [1+1], [2])
dp[3] = 4 (네 가지 경우: [1+1+1], [2+1], [1+2], [3])

다이나믹 프로그래밍(동적 계획법) 설명:
다이나믹 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나누어 푸는 기법입니다. 위에서 언급한 점화식을 사용하여 각 숫자에 대한 경우의 수를 계산해 나가면 됩니다. 이를 통해 중복 계산을 피하고 효율적으로 결과를 도출할 수 있습니다.

파이썬 코드 구현:
아래는 위에서 설명한 내용을 바탕으로 작성된 파이썬 코드입니다.

import sys

n = int(input())
dp = [0] * 11  # 최대 입력값인 N=10까지 고려하여 배열 생성
dp[1], dp[2], dp[3] = 1, 2, 4  # 초기값 설정

for i in range(4, 11):
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

for _ in range(n):
    testNum = int(sys.stdin.readline())
    print(dp[testNum])

이 코드는 먼저 입력받은 테스트 케이스 개수만큼 반복하여 각 테스트 케이스에 대해 결과를 출력합니다. dp 배열은 다이나믹 프로그래밍을 위해 사용되며, 초기값들을 설정해줍니다.

코드 실행 예시:
코드를 실행하면 사용자로부터 입력받은 값에 따라 해당하는 조합의 개수를 출력하게 됩니다. 예를 들어:

입력:
3
4
7
10

출력:
7
44
274

이렇게 여러 테스트 케이스에 대한 결과를 쉽게 확인할 수 있습니다.

마무리:
이번 포스팅에서는 백준 9095번 문제인 '1, 2, 3 더하기'에 대해 알아보았습니다. 다이나믹 프로그래밍 기법을 통해 효율적으로 문제를 해결하는 방법도 배웠습니다. 이 문제는 기초적인 DP 문제로, 더 복잡한 알고리즘 문제를 해결하는 데 좋은 시작점이 될 수 있습니다.