[백준][11052번, 16194번][Python] 카드 구매하기 1,2 && 블로그 닉값의 위험성

주의! 이 문제는 블로그 닉네임 값을 한 문제이며 닉값하지 말자는 반성문입니다.

 

 두 문제의 차이는 간단하다. 최대를 구하냐, 최소를 구하냐 정도뿐이다.

dp문제에서 dp배열을 초기화할때는 (나는) 값을 0으로 한다. 별 의미도 모르는채로 초기화한다.

 

 

 

방법은 다음과 같다.

dp[n] = n개의 카드를 샀을때의 최댓값, 최솟값을 구한다.

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

 

이때, 이 문제는 i 개의 카드를 살때 최댓값을 구하는 첫번째 반복문과,

1<=j<=i 를 돌며 i 전에 0-i 전 상태와 비교하는 두번째 반복문으로 이루어져 있다.

 

dp[i] = max(dp[i], dp[i-j]+arr[j]) ->11052

dp[i] = min(dp[i], dp[i-j]+arr[j]) -> 16149

은 i번째 까지 샀을때는 == j번째 카드팩을 샀을때 값이 최대/최소가 될까? 를 판별하는 식이다.

 

이건 간단한데, 여기서 닉값을 했다가 시간을 버렸다.

[0 for _ in range(n+1)] ->11052 최대

[0]+[912341234 for _ in range(n)] -> 16149 최소

 

여기서 왜 달라질까? 를 고민하지 않고 그냥 베꼈다가 털렸다.

왜 dp 배열을 초기화할때 최소일경우 값을 넣어줘야 할까? 

왜냐면, dp 배열과 비교를 하기 때문이다.

최댓값을 찾는 문제에서는 max를 쓰기 때문에 0을 써야 카드값이 무조건 >0 이기 때문에 문제를 맞출수 있는것이고,

최솟값을 찾는 문제에서는 min 을 쓰기 때문에 초기화 된 값이 많이 커야 첫번째 dp 연산에서 제대로 된 값을 얻을 수 있는 것이다.

 

 

 

 

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

11052번: 카드 구매하기

 

import sys

n = int(sys.stdin.readline())
arr =[0]+ [int(i) for i in sys.stdin.readline().split()]
dp = [0 for _ in range(n+1)] 

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


print(dp[-1])

문제 : https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

 

 

import sys

n = int(sys.stdin.readline())
arr =[0]+[int(i) for i in sys.stdin.readline().split()]
dp = [0]+[912341234 for _ in range(n)] #912341234 = Nothing-up-my-sleeve number

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


print(dp[-1])