목록dp (1)

하나씩 알아가기

[BOJ_11052] 카드 구매하기

가장 첫번째 예시를 보면 1을 네 장 사서 4가 되는 것 보다 두장 짜리를 두 번 사서 4를 만드는 것이 4 < 5 * 2 로 금액이 더 큰 것을 알 수 있습니다. 작은 문제로 나눠서 생각하는 것이 중요합니다. 예를 들어 세번째 카드를 구매하면 N개 중 3이 소모되는 것 입니다. 그러면 나머지 N-3개에 대한 dp를 출력하면 됩니다. dp를 갱신시켜나가는데 현재카드와 [N-현재카드의 번호]의 dp값을 비교해서 더 큰 것으로 갱신시키면 됩니다. n = int(input()) card = list(map(int, input().split())) card.insert(0, 0) dp = [0 for _ in range(n+1)] for i in range(1, n+1): for j in range(1, i+1..
알고리즘 2021. 2. 14. 18:01
이전 Prev 1 Next 다음