2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 분석 [2624] 동전 바꿔주기 (DP) 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각..

분석 1. 2차원 배열 : 공간복잡도 안좋음 2. 1 차원 배열 (역방향) : max 값 비교 3. DFS 풀이

분석 더보기

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 분석 가방에 최대 Mkg 까지 담을 수 있을 때, dp[i][j] = 가방에 담은 물건의 무게 합이 i일 때, 처음 j개의 물건 중 담을 수 있는 최대 가치 ( 1 < i

""" 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치 한 종류의 보석을 여러 번 가방에 담을 수 있 다는 뜻입니다. 가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다. 첫 번째 줄은 보석 종류의 개수, 가방에 담을 수 있는 무게의 한계값 두 번째 줄부터 각 보석의 무게와 가치 4 11 5 12 3 8 6 14 4 8 """ import sys input=sys.stdin.readline n,m=map(int, input().split()) d=[0]*(m+1..

bottom up """ 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1,1)격자에서 (N,N)까지 가는데 드는 에너지의 최소량 만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면 3 2 5 2 3 4 6 5 2 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. 5 3 7 2 1 9 5 8 3 9 2 5 3 1 2 3 5 4 3 2 1 1 7 5 ..