BOJ 11052: 카드 구매하기

안녕하세요! 23살 무니화니로 찾아뵙습니다!

새해 복 많이 받으시고 항상 즐코딩하십쇼!

---

BOJ 11052: 카드 구매하기

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

이 문제를 읽자마자, 굉장히 복잡하겠다는 생각이 들었다.

사실 근데 문제만 요란하지, 푸는 문제는 다이내믹 프로그래밍 그 자체로 풀 수 있었다.

 

n=int(input())
cards=[0]+list(map(int,input().split()))
prices=[0]*(n+1)

for i in range(1,n+1):
  for j in range(1,i+1):
    prices[i]=max(prices[i],prices[i-j]+cards[j])

print(prices[i])

우선 입력되는 카드의 값을 cards에 넣어주고, 각자 카드 n장을 살 때 제일 비싸게 살 수 있는 방법을 prices에 넣는다.

그리고, 이미 prices에 있는 가격으로 사는 것이 비싼지, 아니면 전에 있는 두 방법을 더해서 사는 방법이 더 비싼지를 prices에 입력한다.

그래서 마지막 인덱스 구해주면 끝!

 

 

어려운 문제일수록, 간단히 생각해서 정리하는 것이 포인트인 것 같다.

 

---

새해 복 많이 받으시고 항상 화이팅하십쇼!