[BOJ] 카드 구매하기(11052) - PYTHON

카드를 총 N장 구매하려고 한다. 이때  카드의 수가 각각 1장부터 N장까지 있는 묶음의 가격이 차례대로 주어질 때, 딱 N장을 구매하기 위해 드는 비용을 최대로 하는 정답을 찾는 문제다.

ex) N = 4, 카드 묶음 = [1, 5, 6, 7] 일 때
이는 1장 묶음을 사는데 드는 비용이 1,
2장 묶음을 사는데 드는 비용이 5,
3장 묶음을 사는데 드는 비용이 6,
4장 묶음을 사는데 드는 비용이 7 이 든다는 것을 의미한다.
4장을 사는데 드는 최대 비용은 2장 묶음을 2번 사서 드는 10이다.

시간 복잡도: O(N^2)

11052번: 카드 구매하기

---

풀이 과정 

카드 N장을 사는데 드는 비용은 다음과 같이 구할 수 있다.

즉 위 예시에서 카드 4장을 구매하는 경우는 다음과 같이 구할 수 있다.
case 1: 카드 1장을 구매하는데 드는 최대 비용 + 카드 3장을 구매하는데 드는 최대 비용
case 2: 카드 2장을 구매하는데 드는 최대 비용 + 카드 2장을 구매하는데 드는 최대 비용

따라서 카드 N장을 사는데 드는 비용을 구하려면 카드 1~N-1장을 사는데 드는 최대 비용을 구하는 과정이 필요하며 이를 배열에 저장하고 활용하는 동적 계획법을 사용해 문제를 해결한다.

최대 비용을 구하는 각 과정에서 최대 N번의 연산이 필요하고 이를 N번 반복해야 하므로 시간 복잡도는 O(N^2)이다.

---

코드

import sys
 
input = sys.stdin.readline
 
N = int(input())
parr = list(map(int, input().split()))
dp = parr[:]
 
for i in range(N):
    for j in range((i + 1) // 2):
        dp[i] = max(dp[i], dp[j] + dp[i - j - 1])
print(dp[N - 1])

 

주석 추가

import sys
 
input = sys.stdin.readline  # 입력 효율화
 
N = int(input())
parr = list(map(int, input().split()))  # 카드 묶음을 사는데 드는 비용 배열로 저장
dp = parr[:]  # 동적계획법을 통해 저장할 비용 배열, 초기값은 입력과 같게 (K장을 구매하기 위해 K장 묶음 구매)
 
for i in range(N):  # 1~N까지 비용을 구하기
    for j in range((i + 1) // 2):  # i를 구매하는데 드는 비용의 최댓값을 구하기 위해 i보다 작은 값들에서 2개씩 짝지어 더해 최댓값 구하기
        dp[i] = max(dp[i], dp[j] + dp[i - j - 1])  # 2개씩 짝지어 더한 값의 최댓값이 dp[i]
print(dp[N - 1])  # N장을 구매하는데 드는 비용의 최대값 출력

---

채점 결과

처음에는 카드 묶음들 중에서 카드 1개당 비용이 높은 묶음 차례로 무조건 사는 것이 유리할 것이라 생각했다. 

하지만 틀리고 나서 다음과 같은 반례가 있음을 알게 됐고. 동적 계획법을 통해 구해야 함을 알게 됐다.

Input:
12
1 1 6 8 11 1 1 1 1 1 1 1
Ans: 25