15989번 1,2,3 더하기 4(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.

관련 문제)

• 2293 동전1
• 2294 동전2

백준) 1,2,3 더하기 4(15989번)

1,2,3 더하기 4

• 문제 설명: 1,2,3 의 합으로 임의의 숫자를 표현하는 방법의 개수를 구하는 문제입니다. 단, 숫자의 순서만 바뀐 경우는 모두 같은 경우로 생각합니다.

문제 설명

문제에서 수열의 크기(N)는 최대 10,000 입니다.
DP를 활용하여 문제를 접근할 것이므로 점화식의 정의를 우선 세워봅시다.

d[n]을 문제의 조건을 만족하는 n의 경우의 수 라고 정의하여봅시다.

그렇다면 d[n]은 마지막 자리에 오는 수가 1,2,3이냐를 기준으로 다음과 같이 표현이 가능합니다.

• d[n]=d[n-1]+d[n-2]+d[n-3]
• d[n]=(마지막자리 1)+(마지막자리 2)+(마지막자리 3)

위의 점화식의 정의에 따라 두가지 방법의 구현 코드를 비교하여 보겠습니다.

구현 과정: 첫 번째 방법

limit=10000+1
d=[0]*limit
d[0]=1
for i in range(limit):
  for k in range(1,3+1):
    if i-k>=0:
      d[i]+=d[i-k]

• d[0] = 1 가지
• d[1] = (1) = 1 가지
• d[2] = (1+1) + (2) = 2 가지
• d[3] = (1+1+1) + (1+2) + (3) = 3 가지
• d[4] = (1+1+1+1) + (2+1+1) + (1+2+1) + (3+1) + (1+1+2) + (2+2) + (1+3) = 7가지

구현 과정: 두 번째 방법

limit=10000+1
d=[0]*limit
d[0]=1
for k in range(1,3+1):
  for i in range(limit):
    if i-k>=0:
      d[i]+=d[i-k]

• d[0] = 1 가지
• d[1] = (1) = 1 가지
• d[2] = (1+1) + (2) = 2 가지
• d[3] = (1+1+1) + (1+2) + (1+2) + (3) = 4 가지
• d[4] = (1+1+1+1) + (1+1+2) + (2+2) + (1+3) = 4 가지

위의 두 가지 구현에서의 차이점이 보이나요?

두 가지 방법 모두 위에서 정의한 점화식의 규칙을 만족하지만 그 결과는 다르게 나타납니다.
그러나 문제의 조건을 만족하는 방법은 두 번째 방법인 것을 확인 할 수 있습니다.
그 이유는, 두 번째 방법의 경우 1,2,3을 사용하는 반복문을 가장 바깥으로 하여 수의 배열이 오름차순으로 정렬되는 효과를 보이기 때문입니다.

따라서 오름차순으로 정렬됨으로 인해 중복되는 경우가 없이 문제의 조건을 완벽하게 만족하게 됩니다.

이러한 아이디어(?)는 처음에는 생각하기 다소 힘들고 두 가지의 차이점을 머릿속으로 명확하게 구별하는 것은 어렵습니다.
그렇기 때문에, 다양한 DP 유형의 문제(다른 유형과 다르게 DP는 많이 풀어서 경험을 쌓는수 밖에 없는것 같아요 ㅠㅠ)를 풀어보고 구현 과정의 일부분은 머리가 아닌 손으로 적으면서 문제를 푸는 습관을 들여봅시다.

전체 구현 코드

import sys
def input(): return sys.stdin.readline().rstrip()

limit = 10000+1
d = [0]*limit
d[0] = 1

for k in range(1, 4):
    for i in range(limit):
        if i-k >= 0:
            d[i] += d[i-k]

t = int(input())
for _ in range(t):
    n = int(input())
    print(d[n])