Archive / BOJ / Python

16194번 카드 구매하기 2

이왜틀?

int n=Integer.parseInt(br.readLine());
int[] pack=new int[n+1];
int[] arr=new int[n+1];
StringTokenizer st=new StringTokenizer(br.readLine()," ");
for(int i=1;i<=n;i++) {
    pack[i] = Integer.parseInt(st.nextToken());
}
for(int i=1;i<=n;i++) {
    for(int j=1;j<=i;j++) {
        arr[i]=Math.max(arr[i],arr[i-j]+pack[j]);
    }
}
bw.write(arr[n]+"");

최소 비용을 구해야하는데 왜 Math.max를 쓴거지?

설계

점화식은 다 짜두었으니 그대로 가져가서 쓰되, min을 쓰도록 한다.

구현

인덱스 범위에 주의한다.

N = int(input())

pack = list(map(int, input().split()))
# 대충 큰 값
dp = [1000000] * (N + 1)
dp[0] = 0

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

print(dp[N])

채점

반성

5년 전 나는 DP 개념을 몰랐을 텐데 나름 점화식을 작성해 풀려고 노력한 모습이 보인다.
장하다 과거의 나

코드 확인

Link to GitHub