2294. [Python]동전 2

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• DP(다이나믹 프로그래밍)

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

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

coins = []
# 동전 저장
for _ in range(n):
    coins.append(int(input()))
# 동전 정렬
coins.sort()
# 동전 중복 제거
coins = set(coins)
# 초기 값으로 10**9 설정 => 동전의 개수가 최소로 사용되기 떄문에 0으로 하면 min 값이 변동됨
dp = [10**9] * 100001
# 동전 순회
for coin in coins:
    # coin 위치 동전 사용횟수 1로 초기화
    dp[coin] = 1
    # coin + 1 부터 시작
    for i in range(coin+1,k+1):
        # i-coin 값이 초기값이 아닌경우
        if dp[i-coin] != 10**9:
            # 현재 dp[i] 값과 dp[i-coin] + 1 한값의 min 값 찾기
            dp[i] = min(dp[i],dp[i-coin] + 1)
# 초기값인 경우 -1 외의 경우 k 인덱스 값 출력
if dp[k] == 10**9:
    print(-1)
else:
    print(dp[k])

 

4. 문제를 풀고난 후 생각

 

• 동전 1을 풀고 비슷한 유형의 DP 문제로 동전 2를 선택했다.
• 이 문제를 풀때 무엇을 DP로 잡을지 고민을 했고, 동전의 사용 개수를 DP로 잡기로 했고 초기값으로 10**9로 큰 값을 설정했다.
• 큰 값을 설정한 이유는 초기값이 0인 경우 min 연산 처리시 0을 가져오기 때문에 초기 설정값을 큰 값으로 처리했고, 이후 coin 의 인덱스 값을 1로 초기화 한 후 반복문을 coin+1 부터 시작하며 min 연산을 통해 위치 값을 갱신했다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(다이나믹 프로그래밍)