일일구름 IT

하 DP 너무 어렵다 ... 정말루 .. 알고리즘 중에 가장 어려운 것 같다.계속해서 알고리즘을 짜는데 너무 어려워서 구글링해서 다른 사람의 코드를 참고하였다. 일단 기본적으로 1개의 카드를 살 때 최대 금액, 2개 카드 최대 금액, ..., n개의 카드를 살 때 최대 금액 이런식으로 점진적으로 풀어 나가야 한다. 점화식부터 찾아보자.dp는 i 개의 카드를 살때 최대 금액을 저장하는 리스트이고 p는 i개의 카드를 살때 정해진 금액이다. dp[0] = 0dp[1] = dp[0] + p[1]dp[2] = max(dp[1] + p[1], dp[0] + p[2])dp[3] = max(dp[2] + p[1], dp[1] + p[2], dp[0] + p[3])dp[4] = max(dp[3] + p[1], dp[2]..

코드 n, k = map(int, input().split()) coin = [] for i in range(n): coin.append(int(input())) sum = [10001 for i in range(k+1)] sum[0] = 0 for i in coin: for j in range(i, k+1): sum[j] = min(sum[j], sum[j-i]+1) if sum[k] == 10001: print(-1) else: print(sum[k]) 동전 1과 비슷한 문제이지만 차이점은 동전의 최소 갯수를 구하는 점과 불가능한 경우엔 -1을 출력하는 것이다. 일단 sum 리스트를 초기값 10001로 초기화 해준다. i==j일 경우에는 동전을 1개만 뽑아도 되므로 sum[0]에 0을 넣어 sum[i..