[골드 V] 2293번. 동전 1

 문제 

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

2293번: 동전 1

 사용 언어 

Python3

 풀이 과정 

NC에서 본 코딩 테스트 문제에 동전 문제가 생각나는 동적 계획법 문제가 있었어서 풀어봤다.

그런데 내가 기억한 문제랑은 다른 유형이었지만 암튼 이것도 점화식 세우기(문제 감 잡기) 너무 어려웠음...

문제의 포인트는 다음과 같았다.

1. 시간 제한이 0.5초, 메모리 제한도 4MB
2. 사용한 동전의 구성이 같으면 순서는 무시한다.

1번 조건 때문에 메모이제이션을 할 때 하나의 리스트 안에서 덮어 씌우는 식으로 빠르게 해결해야 한다.이건 이 문제뿐만 아니라 항상 동적 계획법을 풀 때 이용해야 할 듯 하다.

또 2번 조건 때문에 나는 고민을 했는데 이중 for문을 사용할 때 평소처럼

전체 dp 리스트를 돌면서 가능한 동전 조합의 경우를 추가하기

로 생각했기 때문이었다. 이러면 겹치는 경우의 수가 생기고 이상해지고 어떻게 구현할지 머리아파진다. 따라서 반대로

전체 동전 종류별로 dp 리스트를 돌면서 가능한 경우를 추가하기

로 구현해야 하는 것이었다.

이전 문제와 다르게 호다닥 채점되더니 뜬 맞았습니다!!

이 문제로 얻은 점은 이중 for문을 구현할 때 뭘 바깥에 둘지 잘 생각해봐야 한다는 것..!

 제출 답안 

# n가지 종류의 동전의 합이 k원이 되도록
# 동전의 개수는 무제한
from sys import stdin

kind, total = map(int, stdin.readline().split())
kindList = []
for _ in range(kind):
    kindList.append(int(stdin.readline()))
# print(kindList)

dp = [0] * (total + 1)
dp[0] = 1
for i in kindList: # 1, 2, 5원짜리 동전
    for j in range(i, total + 1):
        if dp[j-i] != 0: 
            dp[j] += dp[j-i]
print(dp[-1])
# print(dp)

 다른 사람 답안 

점화식 세우기 감이 안왔다는 거 빼면 새로 배운 내용은 없어서 또 다른 코드를 찾아보았다.

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    dp = [1] + [0] * k
    for _ in range(n):
        coin = int(input())
        for j in range(coin, k + 1):
            if dp[j - coin] == 0:
                continue
            dp[j] += dp[j - coin]
    sys.stdout.write('{}'.format(dp[-1]))
main()

출처: 백준 채점 현황

 

2년 전 코드라서 .format 출력 형식을 사용하신 것 빼고 아주 깔끔한 것 같다...

 sys.stdout.write 를 사용하신 이유가 궁금한데 출력할 게 많다면 print보다 저게 더 빠른걸까?

구글링해도 시간복잡도 비교는 못찾아서 나중에 출력 조건이 많은 문제에서 시험해보고 싶다.

 

어쨌든 큰 차이는 내가 따로 계산한 for문을 하나로 합친 로직이라는 점이다.

그리고  dp[j - coin] == 0 인 경우에는 더하는 계산을 건너뛰게 해줘서 시간이 더 적게 소요됐을 것 같다.

나도 그 부분을 추가해봤더니 조금 줄어들었다.

dp 초기화도  [1] + [0] * k 라는 방식이 마음에 든다. (dp[0] 바꿔치기가 더 빠르긴 할수도?)