[백준 11052번][실버1] 카드 구매하기 (파이썬)

---

문제출처

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

11052번: 카드 구매하기

---

문제를 스스로 해결하였는가? -> O

 단계별로 풀어보기에서는 알고리즘 분류가 정해져 있어서 대충 어떻게 접근해야할지 감이 오는 문제들이 많았다. 특히 DP를 풀때는 왜 이문제가 DP인지 따지지 않고 바로 규칙성을 찾는 방식으로 문제를 풀어왔다. 단계별 풀어보기에서 벗어나 처음으로 풀어보는 DP 문제인데 역시나 DP 문제임을 알아차리지 못했다... 알고리즘 분류에 DP라는 걸 참고하니 생각보다 쉽게 풀렸다. 무튼 다음엔 DP 문제를 빨리 알아차리길 기대하며 문제 풀이과정을 정리한다.

---

필요한 배경지식

• dp

---

주의할 점

• dp임을 깨닫지 못하면 모든 경우의 수를 따지는 미친 짓을 해버릴 수도 있다.

---

풀이과정

 음... 나름 정리한다고 했는데 깔끔하지 못한거 같다.. 무튼 핵심은 분홍 형광 부분인데, n=4일 때 모든 경우의 수 5개를 다 비교하는게 아니라 n=3일 때 계산된 dp값을 이용한다는 거다.

---

전체 코드

n = int(input())
num_list = [0] + list(map(int, input().split(' ')))
dp = [0] * (n+1)
dp[1] = num_list[1]
for i in range(2, n+1):
    tmp = []
    for j in range(1, i//2+1):
        tmp.append(dp[j] + dp[i-j])
    dp[i] = max(num_list[i], max(tmp))
print(dp[-1])​

---