[백준 11052번-파이썬]카드 구매하기

백준 (BOJ) 11052번
https://www.acmicpc.net/problem/11052

사용언어 : PYTHON

1.문제

2.풀이

최적해(최댓값)을 구하는 문제이므로 다이나믹 프로그래밍을 사용하여 풀 수 있었다.

최적해의 일부분이 그 부분에 대한 최적해가 DP 순환식을 세우는 출발점임을 생각했다.

N이 4이고 P1=1, P2=5, P3=6, P4=7인 경우

최댓값 = max(P4를 선택하지 않은 경우, P4를 선택한 경우)이다.

이때 P4를 선택하면 N의 갯수를 모두 채우기 때문에 P4하나만 살 수 있다.

따라서 max{(P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값, 7}이 된다.

---

위 최적해의 일부분 (P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값 = (P3를 선택하지 않는 경우, P3를 최소 하나 선택한 경우)이다.

이때 P3를 최소 하나 선택한 경우 N(=4)-3 = 1 즉 P1만 살 수 있다.

따라서 max{(P1,P2)의 조합을 이용해서 4를 만들 수 있는 최댓값, 1+6}이 된다.

---

위 최적해의 일부분 (P1,P2)의 조합을 이용해서 4를 만들 수 있는 최댓값 = (P2를 선택하지 않는경우, P2를 최소 하나 선택한 경우)이다.

P2를 선택하지 않는경우는 P1을 4개 사는 경우밖에 없다.

P2를 최소 하나 선택한 경우 N(=4)-2 = 2 즉 (P1,P2)를 이용해서 2를 만들 수 있는 최댓값이 된다.

따라서 max{1*4, (P1,P2)를 이용해서 2를 만들 수 있는 최댓값}이 된다.

---

위 최적해의 일부분 (P1,P2)의 조합을 이용해서 2를 만들 수 있는 최댓값 = (P2를 선택하지 않은 경우, P2를 최소 하나 선택한 경우)이다.

P2를 선택하지 않은 경우는 P1을 2개사는 경우밖에 없다.

P2를 최소 하나 선택한 경우는 P2하나를 사는 경우밖에 없다.

따라서 max{1*2, 5} 가 된다.

2-1.순환식을 세우기

카드 갯수가 1개인 경우(i=1) p1밖에 구매할 수 없다.
주어진 카드가 하나도 없으면(j=0) 최댓값은 0이다.
주어진 카드가 1개(j=1)이면 최댓값은 P1 * i 이다.
그렇지 않은경우 위에서 예를 들어 설명한 바를 순환식으로 나타내었다.

2-2.base case로 수렴하는지 확인

j-1, i-j 를 반복하면
i=1, i=0, j=1인 base case로 수렴하게 된다.

2-3.순환식을 계산

bottom-up 방식(순환식의 오른쪽에 등장하는 값이 왼쪽에 등장하는 값보다 먼저 계산)으로 연산을 하려면 빨간색 화살표와 같이 행우선 순서대로 계산하면 된다.

이때 순환식에는 나타나지 않았는데 i < j 인경우 D(i,j) = D(i,i)가 된다.
예를들어 D(3,5) 즉 카드 3개를 구매하는데 P1,P2,P3,P4,P5가 있다면 P4와 P5는 3개를 초과하기 때문에 구매할 수 없고 P1,P2,P3만 구매할 수 있기 때문이다.

3.코드

import sys
input = sys.stdin.readline

N=int(input())
P=list(map(int,input().split()))
P.insert(0,0)

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

for j in range(1,N+1):
    l[1][j]=P[1]

for i in range(1,N+1):
    l[i][1] = P[1]*i


for i in range(2,N+1):
    for j in range(2,N+1):
        if i < j:
            l[i][j]=l[i][i]
        else:
            l[i][j] = max(l[i][j-1],l[i-j][j] + P[j])

print(l[N][N])