BOJ 9095 1, 2, 3 더하기

태그

다이나믹 프로그래밍

URL

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

문제 설명

•

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

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

0<n<110 < n < 110<n<11

문제 풀이

•

접근 1 브루트 포스 (완전 탐색) - O(3n)O(3^n)O(3n)

◦

nnn을 만들기 위해 1, 2, 3을 계속 더하는 모든 방법을 시도하는 방식

◦

재귀적으로 모든 경우를 탐색하므로, 트리의 깊이가 O(n)O(n)O(n)이고, 각 노드에서 3개의 분기를 탐색하므로 시간 복잡도는 O(3n)O(3^n)O(3n)

▪

즉, n=10n = 10n=10이면 최악의 경우 약 310=59,0493^{10} = 59,049310=59,049 번 연산이 필요

◦

이 문제에서 n≤10n ≤ 10n≤10 이므로 엄청난 연산량이 필요하지는 않지만, 더 효율적인 풀이를 떠올릴 필요가 있다.

•

접근 2 DP - O(n)O(n)O(n)

◦

DP를 사용하면 중복 계산을 피하고 O(n)O(n)O(n)으로 문제를 해결할 수 있다.

◦

DP 테이블 정의

▪

dp[n]=dp[n] =dp[n]=  정수 n을 1, 2, 3의 합으로 나타내는 방법의 수

◦

DP 관계식

▪

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

◦

초기값 처리

▪

점화식을 적용하려면 최소한 dp[1],dp[2],dp[3]dp[1], dp[2], dp[3]dp[1],dp[2],dp[3]의 값이 있어야 한다.

▪

dp[1]=1dp[1] = 1dp[1]=1

▪

dp[2]=2dp[2] = 2dp[2]=2

▪

dp[3]=4dp[3] = 4dp[3]=4

풀이 코드

접근 1 브루트 포스 (완전 탐색) - O(3n)O(3^n)O(3n)

•

접근 2 DP - O(n)O(n)O(n)

def count_ways(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    
    # DP 테이블 생성
    dp = [0] * (n + 1)
    dp[1], dp[2], dp[3] = 1, 2, 4  # 초기값
    
    # 점화식 적용
    for i in range(4, n + 1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
    return dp[n]

T = int(input())
for _ in range(T):
    n = int(input())
    print(count_ways(n))
Python
복사