반응형
이 문제는 아래 문제와 비슷한 문제 방식이다!
2022.03.30 - [백준] - 11052번 파이썬
먼저 dp를 이용하기 위해 p 리스트를 만든다 p의 값에는 deepcopy를 이용해 ary값과 동일하게 넣어준다.
그 다음 1부터 n까지 반복해서 i번째 카드와 num-i번째 dp값을 더한 값을 temp리스트에 넣어준다
(예제로 봤을 때 카드 한개가 들어있는 팩ary[0]과 3개의 카드를 구매하는 최솟값 dp[3]으로 생각하면 됩니다!!)
temp에 있는 값과 num개가 들어있는 팩 하나를 사는 경우 중 더 작은 값을 p[num]에 저장한다
이걸 n까지 반복하면 n개를 구매할때 최솟값을 구할 수 있다.
from cmath import sqrt
import sys,copy
input = sys.stdin.readline
n=int(input())
ary=list(map(int,input().split()))
p=[0]+copy.deepcopy(ary)
for num in range(1,n+1):
temp=[]
for i in range(1,num):
temp.append(p[num-i]+ary[i-1])
if temp:
p[num]=min(p[num],min(temp))
print(p[n])
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
1890번 파이썬 (0) | 2022.04.11 |
---|---|
2225번 파이썬 (0) | 2022.04.10 |
4948번 파이썬 (0) | 2022.04.09 |
2293번 파이썬 (0) | 2022.04.09 |
9461번 파이썬 (0) | 2022.04.09 |