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

DP 문제 

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

---

접근 방식

1, 2, 3 더하기 문제와 다른점

• 1, 2, 3 더하기 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 순열 문제이다.
  • 아래 두가지 경우는 각각 다른 경우이다.
  • 1+2+1
  • 2+1+1
• 1, 2, 3 더하기 4 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 조합 문제이다.
  • 아래 두가지 경우는 같은 경우이다.
  • 1+2+1
  • 2+1+1

동전 문제와 같은점

• 동전 문제는 주어진 동전의 금액을 활용하여, 그 금액의 합이 k원이 되도록 만드는 조합 문제이다.
• 이 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 조합 문제이다.

따라서, 동전 문제와 같은 방법으로 문제를 풀 수 있다.

---

💡 풀이코드 (성공 - 2차원 배열)

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

def count_ways(n):
    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(4)]
    dp[0][0] = 1
    dp[1][0] = 1  
    dp[2][0] = 1
    dp[3][0] = 1

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

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

 

초기화

• dp 배열을 (3 + 1) X (n + 1) 크기로 만든다.
• dp[i][0]을 1로 초기화해준다. 이는, 숫자 i를 이용해 0을 만드는 가짓수가 1개임을 의미한다.
  • 1을 이용해 합 0을 만드는 가짓수 = 1 (1을 사용 안하는 가짓수 1가지)
  • 2을 이용해 합 0을 만드는 가짓수 = 1
  • 3을 이용해 합 0을 만드는 가짓수 = 1

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

 

점화식

dp[i][j] = dp[i][j - i] + dp[i - 1][j]

= i개의 수를 사용하여 합이 j인 수를 만드는 가짓수

= i개의 수를 사용하여 합이 j-i인 수를 만드는 가짓수(1, 2, 3을 무한정 사용 가능하므로) + i - 1개의 수를 사용하여 합이 j인 수를 만드는 가짓수

= i번째 수를 적어도 하나 사용하는 가짓수 + i번째 수를 사용하지 않는 가짓수

dp[i][j] = dp[i][j - i] + dp[i - 1][j]

---

💡 풀이코드 (성공 - 1차원 배열)

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


def sol(n):
    dp = [0] * (n + 1)
    dp[0] = 1

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

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

 

초기화

dp 배열을 만들고, dp[0]을 1로 초기화해준다. 이는, 숫자 i개(1, 2, 3)를 이용해 0을 만드는 가짓수가 1개임을 의미한다.

dp = [0] * (n + 1)
dp[0] = 1

 

점화식

dp[j] += dp[j - i]

= i개의 수를 사용하여 합이 j인 수를 만드는 가짓수

= j를 만들기 위해 마지막에 숫자 i를 더했다고 가정할 때, 그 이전에 j - i를 만드는 방법의 수를 더해주는 방식

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

---

순열 VS 조합

1) 순열 코드

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)

 

2) 조합 코드 (풀이코드)

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


def sol(n):
    dp = [0] * (n + 1)
    dp[0] = 1

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

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

차이점

차이점은 바로 이중 for문에 있다.

• 1번 코드에서는 합이 i 되는 경우의 수를 구하기 위해 두번째  for문을 돌며 j (1, 2, 3)을 차례대로 계산한다. 
  • 이 방식은 i에 대해 동시에 1, 2, 3을 사용해 계산하는 방식이다.
  • 즉, 특정 합이 되 ㄹ수 있는 모든 경우의 수가 한 번에 고려된다.
  • 중복된 경우의 수가 포함되는 순열이다.
• 2번 코드에서는 i (1, 2, 3)을 각각 이용하여 두번째 for문을 돌며 합이 j 되는 경우의 수를 계산한다.
  • 즉, 1을 사용해서 경우의 수를 먼저 구한 다음, 2를 사용해서 그 위에 더 가능한 경우의 수를 계산하고, 마지막으로 3을 사용해서 그 위에 더 가능한 경우의 수를 계산하는 방식입니다. 이 경우 작은 숫자부터 순차적으로 누적해 가는 형태이다.
  • 다시 말해, 각 숫자에 대한 영향을 순차적으로 반영해가는 방식이다. 작은 숫자의 경우의 수가 먼저 계산되고,
    그 뒤에 더 큰 숫자들의 조합이 추가된다.
  • 중복된 경우의 수가 방지되는 조합이다.

---

참고문헌

https://velog.io/@dhelee/%EB%B0%B1%EC%A4%80-15989%EB%B2%88-123-%EB%8D%94%ED%95%98%EA%B8%B0-4-Python-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8DDP

[백준] 15989번: 1,2,3 더하기 4 / Python / 다이나믹 프로그래밍(DP)