백준 11052 : 카드 구매하기 (파이썬, python)

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

11052번: 카드 구매하기

 

단순히 개수별로 최대값을 구하면 되겠다고 생각하여 간단하게 풀었으나 마지막 예제에서 오답이나왔다.

다시 생각해서 마지막 예제만을 고려하니 다른 답이 틀리게 나왔다 ㅠㅠ

 

틀린풀이

# 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
#
# 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

n = int(input())

card_list = list(map(int, input().split()))
# print(f' card[0] : {card_list[0]}')
# print(card_list)
ans = []
for i in range(1, n+1):
    ans.append((n//i)*card_list[i-1])

# print(ans)
# print(int(max(ans)))

max_num = int(max(ans))
max_index = ans.index(max_num)
# print("index : "  , ans.index(max_num))
if n - ans.index(max_num)>0:
    ans.pop(ans.index(max_num))
    max_num = int(max(ans))
    # print(max_num)
    # max_index = ans.index(max_num)
    # print(n-ans.index(max_num)-2)
    # print("card : " , card_list[n - ans.index(max_num)-2]) # 4 - 3 - 1
    max_num += card_list[n - ans.index(max_num)-2]
# print(f'ans : {ans}')
# print(f'max_num : {max_num}')
# print(f'idx : {max_index}')

print(max_num)

dp를 사용하면 쉽게 풀 수 있었다.

 

참고 블로그(https://pacific-ocean.tistory.com/66)

n = int(input())
d = [0] * (n + 1)
p = [0] + list(map(int, input().split()))
d[1] = p[1]
for i in range(2, n + 1):
    for j in range(1, i + 1):
        if d[i] < d[i - j] + p[j]:
            d[i] = d[i - j] + p[j]
print(d[n])

d[n]의 배열은 n개의 최댓값을 저장하는 배열이다.

 

p의 배열은 입력을 받는 각각의 가격이다. 헷갈리지 않게 p[0]에는 0을 넣어주고 p[1]부터 값을 받는다.

 

d[1] 즉, 1개를 산다고 했을때의 최댓값은 당연하게도 p[1]이다.

 

이제 d[2]부터 최댓값을 살펴보자.

 

d[2] = d[1] + p[1] or d[0] + p[2]

d[3] = d[2] + p[1] or d[1] + p[2] or d[0] + p[3]

d[4] = d[3] + p[1] or d[2] + p[2] or d[1] + p[3] or d[0] + p[4]

 

이렇게 될 수 있다.

 

여기서 []안에 들어가는 숫자는 모두 카드의 개수를 의미한다.

 

즉, 모든 경우의 수를 계산해서(조건에 맞게) 최댓값을 구하는 문제이다.