동전 1 (2293번) - 백준 (BOJ)

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

2293번: 동전 1

 

백준 - 동전 1 (2293번)

 

난이도 : Gold 5

알고리즘 : Dynamic Programming

풀이 소요 시간 : 60분

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    n, k = map(int, input().split())
    memo = [0] * (k+1)
    memo[0] = 1
    for _ in range(n):
        coin = int(input())
        for i in range(k-coin+1):
            memo[i+coin] += memo[i]
    print(memo[-1])

 

예전에 풀었던 문제였는데, Knapsack과 결이 비슷하다.

 

n이 100까지라 그냥 DFS로 풀릴 줄 알았는데, 얄짤없이 "시간초과"가 떠버렸다.

그래서 DP를 적용했더니 잘 풀렸다.

 

처음에는 동전을 역순으로 정렬해서 풀었는데,

굳이 정렬을 안해도 된다는 걸 깨달았다.

 

처음에 DFS로 풀다가 시간을 꽤나 잡아먹었다;;