공부 124일차: 백준 16194번 카드 구매하기 2 자바 java

16194 카드 구매하기 2

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

16194번: 카드 구매하기 2

 

 

 

 

---

백준 16194번 문제 카드 구매하기

---

문제

---

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/242

공부 123일차: 백준 11052번 카드 구매하기 자바 java

최대값을 구하는 이 문제에서 최소값을 구해야 한다는 것만 바뀐 문제다

 

그렇다고 Math.max()를 Math.min()으로만 바꾸면 되는 문제는 아니다

왜냐하면 정수 배열은 값을 따로 설정해주지 않으면 모든 값이 0으로 초기화되어서,

dp[] 배열에 값을 주지 않으면 어떤 값을 집어넣어도 0이 나오기 때문이다

 

문제에 주어진 예제 입력 중 하나를 가지고 예시를 보려고 한다

5
10 9 8 7 6

pack[] = {0, 10, 9, 8, 7, 6}

dp[1] = 10 
(pack[1]. 카드 1개를 사는 경우는 하나밖에 없다)

dp[2] = 9 / 10+10
(pack[2] 한 번에 카드 2개를 사거나 / 앞서 구한 dp[1]에 카드 1개팩(pack[1])을 추가한다)

dp[3] = 8 / 10+9 / 9+10
(pack[3] 한 번에 카드 3개를 사거나 / 앞서 구한 dp[1]에 카드 2개팩(pack[2])을 추가하거나 / 앞서 구한 dp[2]에 카드 1개팩을 추가한다)

 

결국 dp[n] = pack[n]과 다른 경우의 수들과 비교해야 함을 알 수 있으므로, dp[]에도 pack[]과 같은 숫자들을 넣어줘야 함을 알 수 있다

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+1];
        int[] pack = new int[n+1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < n+1; i++){
            pack[i] = dp[i] = Integer.parseInt(st.nextToken());    
        }
        //System.out.println(Arrays.toString(pack));
        
        dp[1] = pack[1];
        for(int i = 1; i < n+1; i++) {
            for(int j = 1; j < i+1; j++) {
                dp[i] = Math.min(dp[i], pack[j]+dp[i-j]);
                //System.out.println("dp["+i+"]: "+dp[i]);
            }
        }
        System.out.println(dp[n]);
    }
 
}
 

 

 

 

 

---

어제와 같은 결의 문제였던 것 치고 오래 걸리긴 했지만.. 방법 찾다보니 또 재밌어서 좋았다