코드

n, k = map(int, input().split())

# 동전의 종류 리스트
coins = [int(input()) for _ in range(n)]

# dp[i] : i원을 만들 수 있는 경우의 수
dp = [0 for _ in range(k+1)]

# 자기 자신을 사용하는 경우의 수에 대해서는 0이 아니라 1이어야 한다
# 5원으로 5원을 표현하는 경우는 0개가 아니라 1개가 존재함
# 따라서 1을 미리 넣어줌
dp[0] = 1

# 주어진 동전 종류에 따른 반복문 수행
for c in coins:
    
    # 범위가 c부터인 이유
    # 만약 c가 5라고 할 때, 5원을 가지고 5보다 작은 금액을
    # 만들 수 있는 방법은 없음
    for i in range(c, k+1):
        
        # i-c의 의미
        # 아래 설명 참고
        dp[i] += dp[i-c]

print(dp[k])

문제 해설

DP 문제.

그리디 알고리즘의 대표인 동전 문제를 DP화 시킨 경우. 이 문제는 그리디와 다르게 동전이 중복이 되므로 생각할 것들이 더 늘어난다. 주어지는 시간 또한 0.5초이므로 상당히 빠른 시간 복잡도를 요구하는 문제이다. 따라서 DP로 문제를 해결해야 한다.

처음 문제를 봤을 때 2차원 리스트로 해결해야 하지 않을까 생각을 하였다. 하지만 메모리 초과 문제가 발생한다는 것을 알았고 1차원으로 어떻게 풀 수 있을지 고민하였으나, 뭔가 알 것 같으면서도 점화식을 파악하는 것이 생각보다 어려웠다…

스티커

위는 문제의 예시를 직접 손으로 풀어봤을 때 나오는 경우의 수들이다.

(빨간 숫자들이 각 k원을 만들 때 가질 수 있는 경우의 수, 즉 DP 테이블에 저장되는 정답)

위의 과정을 보면서 DP 테이블의 점화식을 세워보자.

  • 1로 k원을 만들 수 있는 경우의 수는 무조건 1개다.

  • n원과 그 이하의 동전으로 k원을 만든다고 할 때, k가 n보다 작은 경우의 수는 무조건 0개다.

  • n원과 그 이하의 동전으로 k원을 만들 수 있는 경우의 수는 k-n원을 만든 경우의 수 누적 경우의 수와 같다.

    • 만약 1원, 2원으로 7원을 만든다고 해보자

    • 7원을 만들 수 있는 경우의 수는 5(7-2)원을 만들 수 있는 모든 경우의 수에 2를 더한 경우와 같다.

    • ex)

    • 스티커

    • 위의 과정으로 구한 경우의 수와, 이전까지 DP에 누적된 합을 더해주면 정답

  • 점화식 : DP[i] += dp[i-j]

되게 단순해 보였던 문제이지만, 생각보다 생각할 것이 많고 헷갈렸다. DP는 아무래도 정규화된 느낌이 아닌, 알고리즘이라기 보단 좀 더 빠른 로직을 찾아주는 스킬(?)에 가까운 느낌이 매번 든다. 그렇기 때문에 많은 연습을 거쳐야만 두렵지 않게 해결할 수 있을 거 같다. 더 많은 문제를 찾아 풀어봐야겠다.

댓글남기기

참고