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

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

 

문제 분석

• n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하라

 

풀이

1. 순서x, 중복o → 중복 조합 (product)
2. dp
   • 뭘 저장해야 할까?
     • 초기조건
     • 2 = 1+1
     • 2 = 2 
       
       
     • 3 = 1+1+1
     • 3 = 1+2
     • 3 = 2+1
     • 3 = 3
   • 새로운 숫자에 대해 다음을 굳이 또 계산할 필요가 없다.
   •  

 

정답 코드

1. 중복 조합

import sys
input = sys.stdin.readline
from itertools import product

tc = int(input())

for _ in range(tc) :
    ans = 1
    n = int(input())

    nums = [1,2,3]

    for i in range(1, n) : # 1을 n번 더하는거 이상은 없음
        for res in product(nums, repeat=i) :
            if sum(res) == n :
                ans += 1
    print(ans)

코드의 시간 복잡도를 분석해 보자.

1. 반복문 및 연산 분석

• tc = int(input()): 테스트 케이스 개수를 입력받는다. (이 부분은 전체 복잡도에 영향을 미치지 않음)
• for _ in range(tc): 테스트 케이스만큼 반복.
• n = int(input()): 정수 nn 입력받음.
• nums = [1,2,3]: 사용할 숫자 리스트 정의.
• for i in range(1, n): 1부터 n−1n-1까지 반복.
  • product(nums, repeat=i): 길이 ii인 숫자 조합을 생성.
  • sum(res) == n을 만족하는 조합을 찾음.

2. itertools.product의 복잡도 분석

product(nums, repeat=i)는 길이 ii의 순열을 생성하며, 가능한 조합 개수는 다음과 같다.

3i3^i

즉, itertools.product는 각 ii에 대해 3i3^i개의 조합을 만든다.

3. 전체 시간 복잡도

각 ii마다 3i3^i개의 조합을 생성하고, 이를 i=1i = 1부터 n−1n-1까지 반복한다.
총 연산량을 계산하면 다음과 같다.

∑i=1n−13i=31+32+⋯+3n−1\sum_{i=1}^{n-1} 3^i = 3^1 + 3^2 + \dots + 3^{n-1}

이것은 등비수열의 합이며, 공식 적용하면:

3n−32\frac{3^n - 3}{2}

즉, 전체 복잡도는 O(3n)O(3^n)에 가깝다.

4. 최악의 경우 ( n=10n = 10 )

O(310)=O(59049)O(3^{10}) = O(59049)

대략 6만 번의 연산이 필요하며, n≤10n \leq 10이므로 현실적으로 실행 가능하지만, nn이 커지면 비효율적이다.

5. 결론

• 시간 복잡도: O(3n)O(3^n)
• 비효율적인 이유: product를 사용하여 모든 조합을 생성한 후 필터링하기 때문
• 개선 방법: 동적 계획법 (DP)을 사용하면 O(n)O(n)에 해결 가능

 

2. DP

import sys
input = sys.stdin.readline

tc = int(input())

for _ in range(tc) :
    n = int(input())
    
    if n == 1 :
        print(1)
        continue
    elif n == 2 : 
        print(2)
        continue
    elif n == 3 :
        print(4) 
        continue

    dp = [0 for _ in range(n+1)]
    
    dp[1] = 1
    dp[2] = 2 # 1+1, 2
    dp[3] = 4

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

    print(dp[n])