백준 16194번 카드 구매하기2

강기호·2023년 2월 9일
0

백준

목록 보기
7/10

문제 링크

전략

  • 최소 비용을 구하는 것이기 때문에 점화식의 리스트 값을 0으로 초기화 하면 처음부터 가장 작은 값이 들어감.
  • 하지만 실제로 점화식 값이 0이 나올 수도 있지만 -1은 절대로 나올 수 없기 때문에 -1로 초기화를 해준다.
  • 그래서 d[i] ==-1인 경우는 값이 수정되지 않은 경우이기 때문에 임시로 계산값을 집어넣고 그 값보다 최소값인 경우가 등장하면 d[i]를 업데이트 해준다.
  • 카드 구매하기1과 같은 방법으로 점화식을 세워서 문제를 푼다.

알고리즘 종류

  • 다이나믹 프로그래밍
import sys

N = int(sys.stdin.readline())
P = [0] + list(map(int , sys.stdin.readline().split()))

d = [-1]*(N+1)
d[0] = 0 
# 이거를 해주지 않으면 d[0]=-1이어서 밑의 점화식에서 d[1] = d[0] + P[1] 할때 1을 빼버림
for i in range(1,N+1):
  for j in range(1,i+1):
    tmp = d[i-j] + P[j]
    if d[i] == -1:
      d[i] = tmp
    elif tmp < d[i]:
      d[i] = tmp
print(d[N])

모범답안

n = int(input())
a = [0] + list(map(int,input().split()))
d = [-1]*(n+1)
d[0] = 0
for i in range(1, n+1):
    for j in range(1, i+1):
        if d[i] == -1 or d[i] > d[i-j]+a[j]:
            d[i] = d[i-j]+a[j]
print(d[n])

0개의 댓글