백준 15989번 1, 2, 3 더하기 4 | python | dp

문제

링크

풀이

너무나도 전형적인 dp 문제!
최적 부분 구조와 중복 부분 문제가 한 눈에 보이기 때문이다.

풀이 방식은 정수 n에 대하여

1로만 1~n까지 만드는 경우의 수
1,2으로 1~n까지 만드는 경우의 수
1,2,3으로 1~n까지 만드는 경우의 수

이런식으로 계속 나아가다 보면 결국 1,2,3으로 n을 만드는 경우의 수를 최종적으로 구할 수 있다.

이러한 문제는 무조건 직접 도식화해서 그려보고 점화식을 찾으면 게임 끝이다.

먼저 dp 테이블은 주어진 입력의 테스트 케이스 중 가장 큰 값+1 크기의 1차원배열을 생성해준다

예제 입력에 따라 풀이를 진행해보자. 주어진 테스트 케이스 중 가장 큰 값은 10이므로 우리는 10을 1,2,3의 합으로 나타내는 방법의 수를 구하면 된다. 다른 테스트 케이스들은 Optimal Substructure에 의해 가장 큰 값인 10을 구하면서 자연스럽게 구해지게 되므로 별도로 고려하지 않아도 된다.

이제 앞서 얘기한대로 1만 가지고 1~10까지 만드는 경우의 수를 생각해보자
dp=[0,1,1,1,1,1,1,1,1,1,1]
위와 같이 업데이트가 될것이다.

이제 1과 2를 가지고 1~10까지 만드는 경우를 생각해보자.
일단 2를 가지고 1을 만들 순 없다. 즉, dp[2]부터 업데이트 될 것이다.
따라서 dp[2]를 살펴보면 1과 2를 가지고 2를 만드는 경우의 수는 1+1, 2 = 2가지이다.
dp[3]의 경우 1+1+1,2+1=2가지 이다
dp[4]의 경우 1+1+1+1,2+1+1,2+2=3가지이다.

자, 이제 여기까지 왔으면 점화식을 바로 찾아낼 줄 알아야한다.
dp[2]는 기존 값에서 2로 만든 경우의 수 1가지(2)가 추가된 것인데, 이는 dp[0]에서 2가 추가된것으로 이해할 수 있다.

단번에 이해가 안된다면 아래를 확인해보자

dp[3]또한 기존 값에서 2로 만든 경우의 수 1가지(1+2)가 추가된 것인데, 이는 dp[1]에서 2가 추가된 것으로 이해할 수 있다

마지막으로 dp[4]까지 확인해보자.
dp[4]는 기존 값에서 2로 만든 경우의 수 2가지(1+1+2, 2+2)가 추가된 것인데, 이는 dp[2]에서 2가 추가된 것으로 이해할 수 있다

그렇다면 점화식은?
dp[i]=dp[i]+dp[i-coin] 이다 🎉

아래는 전체코드이다. 참고로 1로만 경우의 수를 만드는 경우엔 n이 무엇이든 모두 경우의 수가 1이므로 애초에 처음 dp 테이블을 만들 때부터 1로 초기화해주었다.

import sys

input = sys.stdin.readline

t = int(input())

arr = [int(input()) for _ in range(t)]

dp = [1] * (max(arr) + 1)


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


for a in arr:
    print(dp[a])

이 정도가 골드 dp 문제라면 얼마나 좋을까 🥲