[백준] 13137 - Exchange Problem

[문제링크]

13137번: Exchange Problem

 

0. 그리디를 이용해 가격 구하기

  - n번 동전의 가치가 w이고, n-1번 동전까지 사용하여 w-1 금액까지는 옳은 해가 구해져 있다면

  - w원 이후의 가격 x에 대해선 ( (x%w)의 최적해 + (x/w) ) 이 최적해이다

  - ex) 한국 동전에 대해, w가 500원일때 650원의 최적해는 (150원의 최적해 + 1) 이다

  - DP는 이 문제에서 항상 옳은 해를 구할 수 있다

  - DP를 이용해 구한 해와 그리디를 이용해 구한 해가 일치한다면, 그리디가 최적해를 구하는 것

  - 그리디를 통해 w ~ 2*w까지 최적해를 구할수 있다고 하면, 2*w ~ 이후에 대해서도 최적해가 보장된다

  - n+1번째 동전의 가치가 2*w보다 작다면 n+1번 동전까지만 최적해를 증명해도 된다

  - 즉, n번째 동전에 대해, min( 2*w(n) , w(n+1) ) 까지 최적해 여부를 검증

 

1. 정답은 기본값 Yes로 두고, 모든 동전에 대해 최적해 일치 여부를 검사한다

 

2. 현재 금액 i가 n번 코인의 화폐가치 w보다 작을 경우, w까지 진행한다

 

3. w부터 min( w*2, w[n+1] ) 금액까지 그리디 방식으로 해를 만든다

 

4. w부터 min( w*2, w[n+1] ) 금액까지 DP방식으로 해를 만들며, 그리디의 해와 비교한다

  - 중간에 불일치하는 값이 존재하면, 답을 No로 바꾸고, break한다

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int[] coin = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			coin[i]=pint(st.nextToken());
		}
		int[] valid = new int[coin[N-1]*2+1];//최대 20만 1
		valid[1]=1;//1원은 항상 1.
		
		String answer = "Yes";
		
		int coinIdx=1;
		for (int i = 1; i < coin[N-1]*2+1 && coinIdx<N; i++) {

			i = Math.min(2*i-1, coin[coinIdx]-1);
			//coin[i]번의 화폐가치까지 정상진행
			while(i<coin[coinIdx]) {
				int realcosti=Integer.MAX_VALUE;
				for (int k = 0; k < coinIdx; k++) {
					if(1 + valid[i-coin[k]] < realcosti)realcosti=1 + valid[i-coin[k]];
				}valid[i++]=realcosti;
			}
			
			//valid[i] ~ 2 i까지 그리디로, +1해서 제작
			int destination = i*2;
			if(coinIdx<N-1)destination = Math.min(i*2, coin[coinIdx+1]);
			for (int j = i; j <= destination; j++) {
				valid[j]=valid[j-i]+1;
			}
			
			//직접 계산해가면서 valid[j]와 계산값이 같은지 비교. 다르면 바로 탈출
			//i-1번까지의 동전만 사용해서 i ~ 2*i의 값들을 계산해보기
			for (int j = i; j <= destination; j++) {
				int realcosti=Integer.MAX_VALUE;
				for (int k = 0; k <= coinIdx; k++) {
					if(1 + valid[j-coin[k]] < realcosti)realcosti=1 + valid[j-coin[k]];
				}
				if(realcosti != valid[j]) {
					answer = "No";
					i=coin[N-1]*2+1;//for문 종료 목적
					break;
				}
			}
			coinIdx++;
		}
		System.out.println(answer);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면