백준 2294. 동전 2

🅰 백준 2294. 동전 2

2294번: 동전 2

✏️ 문제 풀이

• coin배열에 사용할 수 있는 동전을 전부 저장한다.
• 이중for문을 이용해서 바깥쪽 for문에는 coin의 개수만큼 반복하고, 안쪽 for문에는 가치의 합인 k만큼 반복을 한다
• 점화식 : if(j-coin[i] >= 0 && D[j-coin[i]!=max_value) : D[j] = min(D[j], 1 + D[j - coin[i]])
• 만약 j를 현재 coin[i]로 계산할 수 있고, 이전에D[j-coin[i]] 의 데이터가 있다면 D[j] 최신화
• 만약 D[k]가 초기값이라면 -1 출력 / 아니면 D[k]에 저장된 값 출력

✏️ 소스코드

package dp;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_실버1_2294_동전2 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int coin[] = new int[n];
		int D[] = new int[k + 1];
		Arrays.fill(D, Integer.MAX_VALUE);
		for (int i = 0; i < n; i++) { // 데이터 입력
			coin[i] = Integer.parseInt(br.readLine());
		}
		D[0] = 0;
		for (int i = 0; i < n; i++) {	// coin의 개수만큼 반복
			for (int j = 1; j <= k; j++) {	// 1부터 k까지 반복
				if (j - coin[i] >= 0 && D[j-coin[i]]!=Integer.MAX_VALUE) {	
                // 만약 coin[i]로 j를 계산할 수 있다면
					D[j] = Math.min(D[j], 1 + D[j - coin[i]]);				
                    // 현재 D[j]와 D[j-coin[i]]에 현재 coin을 1개 추가한 값의 최소값 저장
				}
			}
		}
		if (D[k] == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(D[k]);
	}
}

 

✅ 후기

• 점화식을 세우는건 아직 어려운것 같다.. 더 많은 dp문제를 풀어봐야겠다