백준 11052 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

문제는 길지만 별거 아니다.

 

이 문제에서 처음으로 든 생각이 있다.

 

현재의 나는 이 문제에 대해 논리적으로 완벽하게 풀어냈다고 믿는다.

 

코드부터 보자

n = int(input())

price = list(map(int,input().split()))

price_val = []

money = 0

for i in range(1,len(price)+1):

    price_val.append(price[i-1]/i)

while n:

    a = price_val.index(max(price_val))+1

    n -= a

    money += price[a-1]

    for i in range(n,len(price_val)):

        price_val[i] = 0

else:

    print(money)

해당 코드를 작성하고 제출했지만, 틀렸다고 나왔다.

 

하지만 나는 코드를 확신했기에 무언가 이상하다고 생각했다.

 

논리상 내 코드는 완벽하다.

 

1. 입력받은 카드의 1장당 가격을 price_val에 저장한다.

2. price_val의 max값을 찾은 후, 해당 인덱스에 해당하는 price를 money에 더해준다.

3. price_val에 더 이상 선택할 수 없는 카드팩의 가격을 0으로 초기화시킨다.

 

이 논리에 나는 흠이 없다고 생각한다.

 

근데 답은 틀렸다.

 

누군가 나에게 가르침을 주었으면 좋겠다.

 

그래서 검색해 봤더니 dp를 사용하란다.

 

근데 dp 없이 내가 푼대로 해도 결과는 같다고 생각한다.

 

시간초과 오류도 아니라 그냥 틀렸다길래 대체 뭐가 문제인지 모르겠다.

 

지금은 복잡한 마음에 글을 두서없이 적어, 읽기 힘들 수 있다.

 

그 부분에 죄송한 마음을 표한다.

 

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

 

이해가 되지 않는 부분을 백준 게시판을 통해 물어봤다.

 

누군가 조언을 줬다.

예제 하나만 들어주셨는데도, 무슨 부분에 오류가 있었는지 이해가 되었다.

 

단순히 평균값이 높은 것만 계산하면, 고려하지 못하는 부분이 생길 수 있다.

 

따라서 해당 문제는 dp 문제이다.

 

코드

N = int(input())

p = [0] + list(map(int,input().split()))

dp = [0 for _ in range(N+1)]

for i in range(1,N+1):

    print(i)

    for k in range(1,i+1):  

        dp[i]=(max(dp[i], dp[i-k] + p[k]))

        print(dp)

print(dp[i])

출처 : https://infinitt.tistory.com/250

백준 (boj) 파이썬 - 11052 번 : 카드 구매하기 (DP)