16194번 파이썬

이 문제는 아래 문제와 비슷한 문제 방식이다!

2022.03.30 - [백준] - 11052번 파이썬

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])