1. 기본 배낭문제
dp 2차원배열 응용
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
dp=[ [0]*(K+1) for i in range(N+1)]
L=[ [0,0]]
for i in range(N):
L.append(list(map(int, input().split())))
for i in range(1,N+1):
for j in range(1,K+1):
weight=L[i][0] ; value=L[i][1]
if j<weight:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=max(dp[i-1][j-weight]+value , dp[i-1][j])
print(dp[N][K])dp 1차원 배열 응용
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[]
for i in range(N):
a,b=map(int,input().split())
L.append([a,b])
dp=[0]*(K+1)
for item in L:
weight,value=item
for i in range(K,weight-1,-1):
dp[i]=max(dp[i-weight]+value , dp[i] )
print(dp[-1])2. 동전문제
동전이 K원이 여러종류 주어질때 중복사용을 허용하면서 W원으로 만들수 있는 모든 경우의 수
import sys
input=sys.stdin.readline
T=int(input())
for i in range(T):
coin=int(input())
L=list(map(int,input().split()))
W=int(input())
dp=[0]*(W+1)
dp[0]=1
for i in range(len(L)):
for j in range(1,W+1):
if j>=L[i]:
dp[j]+=dp[j-L[i]]
print(dp[W])동전 N원이 종류별로 있을때 중복을 사용해서 K원을 만들수 있는 최소한의 동전 사용 개수
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[]
for i in range(N):
a=int(input())
L.append(a)
dp=[0]*(K+1)
for i in range(1,K+1):
a=[]
for j in L:
if i>=j and dp[i-j]!=-1:
a.append(dp[i-j])
if not a:
dp[i]=-1
else:
dp[i]=min(a)+1
print(dp[K])
3. 호텔문제
호텔의 고객을 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값
import sys
input=sys.stdin.readline
C,N=map(int,input().split())
L=[]
for i in range(N):
L.append(list(map(int,input().split())))
L.sort(key=lambda x:x[0])
dp = [1000000] * (C + 100)
dp[0]=0
for weight,value in L:
for i in range(value,C+100):
dp[i]=min(dp[i-value]+weight,dp[i])
print(min(dp[C:]))
4. 앱 문제
필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
A=[0]+ list(map(int,input().split())) #weight
C=[0]+ list(map(int,input().split())) #value
dp=[ [0]*(sum(C)+1) for i in range(N+1) ]
result=sum(C)
for i in range(1,N+1):
weight=C[i] ; value=A[i]
for j in range(1,sum(C)+1): #j가 value 역할을 함.
if j<weight:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=max(dp[i-1][j-weight]+value , dp[i-1][j])
if dp[i][j]>=M:
result=min(result,j)
if M!=0:
print(result)
else:
print(0)
"""
dp[i][j]는 i번째 앱까지 중 j코스트로 얻을 수 있는 최대의 byte를 의미한다.
j코스로 최대 바이트를 얻었을때 - > 그때 j는 최소값이 되므로 result에 저장한다.
"""5. 커피 문제
N개의 물건이있고 물건을 하나만 써서 총 합이 K가 되기 위해서 필요한 물건의 최소 개수
N,K=map(int,input().split())
L=list(map(int,input().split()))
L.insert(0,0)
dp=[ [0]*(K+1) for _ in range(N+1) ]
for i in range(1,K+1):
dp[0][i]=int(1e9)
for i in range(1,N+1):
for j in range(1,K+1):
if j>=L[i]:
dp[i][j]=min(dp[i-1][j] , dp[i-1][j-L[i]]+1)
else:
dp[i][j]=dp[i-1][j]
if dp[N][K]==int(1e9):
print(-1)
else:
print(dp[N][K])6. 배수 공사 문제
파이프의 길이와 개수가 주어질때 합친 파이프의 길이 x를 만들 수 있는 방법의 수
import sys
input=sys.stdin.readline
N,X=map(int,input().split())
L=[]
dp=[0]*(X+1)
for i in range(N):
a,b=map(int,input().split())
L.append([a,b])
dp[0]=1
for i in range(N):
for j in range(X,-1,-1):
check=0
for _ in range(L[i][1]):
check+=L[i][0]
if j>=check:
dp[j]+=dp[j-check]
print(dp[X])7. 양팔 저울 문제
재귀 풀이
import sys
input=sys.stdin.readline
def Scale(N_list,N,Now,left,right,possible):
check=abs(left-right)
if check not in possible:
possible.append(check)
if Now==N:
return 0
if dp[Now][check]==0:
# 저울의 왼쪽에 놓는경우
Scale(N_list,N,Now+1,left+N_list[Now],right,possible)
# 저울의 오른쪽에 놓는경우
Scale(N_list,N,Now+1,left,right+N_list[Now], possible)
# 저울에 아예 안놓는경우
Scale(N_list,N,Now+1,left,right,possible)
dp[Now][check]=1
N=int(input())
N_list=list(map(int,input().split()))
M=int(input())
M_list=list(map(int,input().split()))
possible=[]
dp=[ [0]*15001 for i in range(N+1) ]
Scale(N_list,N,0,0,0,possible)
for i in range(len(M_list)):
if M_list[i] in possible:
print("Y" , end=" ")
else:
print("N" , end=" ")
2중반복문 풀이
"""
처음에는 아무것도 두지 않는 경우 확인.
두번째는 왼쪽에 설탕을 넣는 경우와 오른쪽에 설탕을 넣는 경우 한번에 확인.
"""
N = int(input()) # N = 추의 개수
w = list(map(int, input().split()))
w.insert(0,-1)
M = int(input()) # M = 확인할 구슬의 개수
marble = list(map(int, input().split()))
dp = [[0]*80001 for _ in range(N+1)]
# dp[i][j] = index i 추까지 고려할때 무게 j의 구슬을 확인 할 수 있는지 여부
# 불가능 = 0, 가능 = 1, 0 ~ 40000 = -40000 ~ 0 / 40001 ~ 80000 = 1 ~ 40000
# 즉 구슬의 무게 + 40000
for i in range(N+1):
dp[i][40000] = 1 # 아무것도 없을때 = 가능
for i in range(1,N+1): # 구슬 선택
for j in range(80001): # 무게
if 0 <= j - w[i] <= 80000:
dp[i][j] = max(dp[i-1][j-w[i]], dp[i-1][j], dp[i][j])
if 0 <= j + w[i] <= 80000:
dp[i][j] = max(dp[i-1][j+w[i]], dp[i-1][j], dp[i][j])
for i in marble:
if dp[N][40000+i] == 1:
print("Y", end = " ")
else:
print("N", end = " ") 
울산대학교 IT융합학부 22학번