[boj 11052][Python] 카드 구매하기

신기한 문제

문제 링크

접근

오늘도 나의 친구... 그리디를 이용하여 접근하였으나 아래와 같은 케이스에서 틀린다.

dbsalvl123 6일 전
--------
@yj10516 님이 반례에 올리신 테스트 케이스가 오답입니다.

12
1 1 6 8 11 1 1 1 1 1 1 1

answer : 25
output : 24
--------
출처: https://www.acmicpc.net/board/view/82364

그리디 알고리즘으로 풀 수 있는 문제의 유형도 어느정도 익힐 필요가 있을 것 같다.

이 문제는 동적계획법[DP] 문제이다!

설명을 찾아 보니 연관된 기본 문제가 떠올랐다.

자연수 n 에 대해 1부터 n까지의 수 혹은 수들의 합으로 나타내는 경우의 수는 몇가지인가? 

예를 들어서,

4	=	4
	=	3 + 1
	=	2 + 2
	=	2 + 1 + 1
	... (생략)

이렇게 표현하는 경우의 수 말이다.

이런 경우에 그 전까지의 수에 대해 갯수를 세어놓은 것을 다음에 이용한다.

카드 구매하기는 그 판단 기준이 가격이 되는 것이다.

코드

# 11052 카드 구매하기

n = int(input())
packs = [0] + list(map(int, input().split()))
# index 맞추려고 앞에 0 끼움
# pricePer = []
# for idx in range(0, len(packs)):
#     pricePer.append(packs[idx]/(idx+1))

# 무지성그리디 - 실패
# DP ? ㅠㅠ
dp = [0 for _ in range(n+1)]
dp[1] = packs[0]    # p1
for i in range(1, n+1):
   for k in range(1, i+1):
       dp[i] = max(dp[i], dp[i-k] + packs[k])
           
print(dp[i])

개당 가격인 pricePer 리스트는 그리디의 흔적이다 ㅠㅠ

아직도 ps 문제 푸는데에 있어서 감을 못 잡은 것 같아서 반성한다....