[Python][백준][2294] 동전 2 (DP)

🍋 문제링크

www.acmicpc.net/problem/2294

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 29028KB

시간 : 320ms

🍉 Code

import sys
input = sys.stdin.readline

def nj(k, coin, dp):
    temp=[]
    for i in coin:
        if k >= i and dp[k-i] != -1:
            temp.append(dp[k-i]+1)

    if len(temp)>0:
        return min(temp)
    else:
        return -1

n, k = map(int, input().split())
coin=[]

for i in range(n):
    coin.append(int(input()))
coin.sort()

dp = [-1 for i in range(k + 1)]

for i in range(1, k+1):
    if i in coin:
        dp[i] = 1
    else:
        dp[i] = nj(i, coin, dp)
    
print(int(dp[k]))

🥝 메모

<푸는 순서>

1. coin 배열의 원소 == dp 의 인덱스 인 부분은 항상 1개이므로 dp[x] = 1
2. coin 배열의 원소 != dp 의 인덱스 인 부분은 dp[x-coin의 원소들]+1 의 최솟값을 넣는다

<python : 정수 두개 입력받기>

import sys
input = sys.stdin.readline

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

<python : 크기 n 배열 입력받기>

import sys
input = sys.stdin.readline

arr=[]
for i in range(n):
    arr.append(int(input()))

<python : 배열 오름차순/내림차순 정렬하기>

arr.sort()    #오름차순
arr.reverse() #내림차순