저번 문제에서 아주 조금 변형된 문제.

16194: 카드 구매하기 2

1. 내 풀이: 성공

import sys

N = int(sys.stdin.readline())
d = [0] * (N+1)
P = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
d[1] = P[1]

for i in range(2, N+1):
    for j in range(1, i+1):
        if d[i] == 0:
            d[i] = d[i-j] + P[j]
        elif (d[i] > d[i-j] + P[j]) and (d[i] != 0):
            d[i] = d[i-j] + P[j]
print(d[N])

왜 d,p 라는 변수를 만들었는지는 설명하지 않겠다 ~ 저번 풀이에 있으니까!
(https://velog.io/@drizzle0171/BOJ-11052-%EC%B9%B4%EB%93%9C-%EA%B5%AC%EB%A7%A4%ED%95%98%EA%B8%B0)

어떤 부분이 바뀌었느냐 하면, 저번에는 구매 금액의 최댓값을 구하는 것이었다면, 이번에는 최솟값을 구하는 것이다. 전체적인 로직은 비슷하기 때문에 처음에

d[i] < d[i-j] + P[j] 의 부분의 부호를 단순히 d[i] > d[i-j] + P[j] 로 바꾸어주었다.

당연히 틀렸다. 0(d의 초기값)보다 작은 수는 없을 테니까.

그래서 만약 일단 d[i]가 0이면 일단 첫 번째로 마주하는 값을 넣기로 했다. 그 부분이 바로

for i in range(2, N+1):
    for j in range(1, i+1):
        if d[i] == 0:
            d[i] = d[i-j] + P[j]

이 부분이다. 그리고 기존에 우리가 생각하는(단순히 부호만 바꾼 조건문) 구절을 elif로 추가해준다.

for i in range(2, N+1):
    for j in range(1, i+1):
        if d[i] == 0:
            d[i] = d[i-j] + P[j]
        elif (d[i] > d[i-j] + P[j]) and (d[i] != 0):
            d[i] = d[i-j] + P[j]

d[i] != 0인 부분은 당연히 없어도 된다. 혹시나 하는 마음에 넣었다.
(없애고 돌려본 결과, 4ms 빠름)

2. 다른 풀이

참고한 블로그는 아래와 같다.
https://hjp845.tistory.com/109

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

dp = [999999999 for i in range(1001)]
dp[0] = 0

for i in range(n + 1):
    for j in range(i + 1):
        dp[i] = min(dp[i], lst[j] + dp[i - j])

print(dp[n])

처음에 min 부분을 보고 "엥? min으로 하면 0일텐데?"라고 생각했다가, 초기값(999999999)이 다른 것을 보고 다른 방식인 것을 알았다. if 문을 두 개 이상 쓰고 싶지 않다면 이 풀이도 좋다고 생각한다. 돌린 결과는,

이와 같다. 아마 이 풀이가

• dp의 range = 1000
• 초기값 9999999

등으로 조금 더 느렸던 것으로 예상한다.

이상 오늘도 신기한 알고리즘의 세계 끝!~