[백준] 9095 : 1, 2, 3 더하기 (파이썬)

DP 문제

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

---

💡 풀이코드 (성공 1)

import sys 
t = int(sys.stdin.readline())

def dynamic(n):
    dp = [0 for _ in range(n + 1)] 

    dp[0] = 1
    dp[1] = 1 
    dp[2] = 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])


for _ in range(t):
    n = int(sys.stdin.readline())
    if n == 0:
        print(1)
    elif n == 1:
        print(1)
    elif n == 2:
        print(2)
    elif n == 3:
        print(4)
    else:
        dynamic(n)

 

접근 방식

4를 1, 2, 3으로 표현하는 방법은 7가지이다.

 

5를 표현하는 방법은 4에서 1을 더하는 방법(7가지) + 3에서 2를 더하는 방법(4가지) + 2에서 3을 더하는 방법(2가지)이 있다.

= 총 13가지(7 + 4 + 2)

 

6를 표현하는 방법은 5에서 1을 더하는 방법(13가지) + 4에서 2를 더하는 방법(7가지) + 3에서 3을 더하는 방법(4가지)이 있다.

= 총 24가지(13 + 7 + 4)

 

점화식

N을 표현하는 방법으로는 다음과 같다.

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

= dp[i-1]에서 1을 더하는 방법 + dp[i-2]에서 2을 더하는 방법 + dp[i-3]에서 3을 더하는 방법 

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

 

동전 문제와 다른점

• 동전 문제는 주어진 동전의 금액을 활용하여, 그 금액의 합이 k원이 되도록 만드는 조합 문제이다.
  • 동전의 구성이 같은데, 순서가 다른 것은 같은 경우이기 때문이다.
• 이 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 순열 문제이다.
  • 아래 두가지 경우는 각각 다른 경우이다.
  • 1+2+1
  • 2+1+1

---

💡 풀이코드 (성공 2)

import sys 
t = int(sys.stdin.readline())

def sol(n):
    dp = [0 for _ in range(n + 1)] 

    dp[0] = 1

    for i in range(1, n + 1):
        for j in range(1, 4):
            if i - j >= 0:
                dp[i] += dp[i - j]
    print(dp[n])


for _ in range(t):
    n = int(sys.stdin.readline())
    sol(n)

---

참고문헌

https://ggasoon2.tistory.com/39

백준 9095번: 1, 2, 3 더하기 (실버3) python