백준 2294 동전2

동전2 링크: www.acmicpc.net/problem/2294

2294번: 동전 2

오늘은 동전2를 풀어보았습니다.

실버1문제인데 규칙이 조금 빡세서 조금오래 걸렸어요 ㅠㅠ

설명을 해드리자면

1, 5, 12의 동전이 있을때

0원은 만들수가 없습니다

왜냐하면 동전의 가치보다 작은 동전은 어떻게해도 만들 수 없기 때문이죠

따라서 위와같은 표가 생성되게 됩니다.

그럼 1원으로 1원부터 15원까지 만들어볼까요

그럼 해당 표처럼 동전의 갯수가 필요하게 됩니다.

여기서 1원과 5원을 가지고 1원부터 15원까지 만들게되면

 

다음과 같이 표가 만들어 지는데요

눈치가 빠르신분들은 벌써 감을 잡았을꺼라고 생각됩니다.

혹시모르니

1원 5원 12원으로 1원부터 15까지 만들면

다음과같이 나오게 됩니다.

따라서 규칙은

arr[index] = arr[index-num]+1이되게 되는데요

만약 1,5,로만 만든다고 했을때 13은 arr[13] = arr[13-5]+1이되게 됩니다 따라서 5개의 동전의 수가 필요하죠

여기서 12까지 추가되면 13에 가장가까운 수는 12이므로 arr[13-12]+1이됩니다 따라서 index13은 2로 바뀌게 되죠

하지만 15의 경우에는 arr[15-12]+1은 4가 됩니다 기존 3보다 큰 수가 나오게 되므로 3은 계속 유지가 됩니다.

 

이를 코드로 짜보면

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, K;// 동전의 갯수, 목표금액
	static int[] coins;
	static int[] answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		coins = new int[N];
		answer = new int[K + 1];
		Arrays.fill(answer, 10001);
		answer[0] = 0;

		for (int n = 0; n < N; n++) {
			coins[n] = Integer.parseInt(br.readLine());
		}

		for (int i = 0; i < N; i++) {
			for (int j = coins[i]; j <= K; j++) {
				int num = answer[j - coins[i]] + 1;
				answer[j] = Math.min(answer[j], num);
			}
		}

		if (answer[K] == 10001) {
			System.out.println(-1);
		} else {
			System.out.println(answer[K]);
		}
	}

}

이렇게 됩니다.