BOJ(카드 구매하기)(11052)

작성일 | In

  • 기존에는 붕어빵 판매하기 였던 것 같은데 카드 구매하기로 변했다. 하지만 문제는 똑같다.

  • 돈을 최대한 많이 지불해서 N개의 카드팩 구매 예정 - 카드 i개가 포함된 카드팩의 가격은 Pi원
  • p1 = 1, p2 = 5, p3 = 6, p4 = 7
  • 카드 4개를 갖기 위해 민규가 지불해야 하는 금액은 10(최대 10)

생각한 방법

  • 만들 수 있는 경우의 수를 다 만들어보고, 그 중 최댓값을 구하면 되지 않을까? DP로 이걸 어떻게 풀지? 카드팩의 가격에 따라 최댓값이 달라지므로, 모든 카드팩의 가격을 비교하여 가장 높은 최댓값을 구해야 한다.
  • d란 배열에 D[i]번째에, 붕어빵 i개를 팔아서 얻을 수 있는 최대의 수익을 구하자.
  • 초기에 입력 받은 배열이 p라고 하자 (가격을 입력 받은 배열)
  • 마지막에 1개를 판매하는 경우는 = d[4] = d[3]+1
  • 그렇게 쭉 가면 d[2] + 2개 팔 때 가격
  • 일반화 시키면
  • 마지막에 1개 판매 하는 경우 d[n-1]+p[1]
  • 마지막에 2개 판매하는 경우 d[n-2]+p[2]
  • 마지막에 i개 판매하는 경우 d[n-i] + p[i]
  • d[i]를 구할 때마다, 1~i가지 판매할 때의 최댓값을 계속 비교하여 찾아야 한다.
N = int(input())
p = [0]+list(map(int, input().split()))
d = [0]*(N+1)
for i in range(1, N+1):
    for j in range(1, i+1):
        d[i] = max(d[i], d[i-j]+p[j])
print(d[N])

참고자료 codeplus 참고블로그

0%