문제 바로가기

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

문제 소개 및 재정의

n가지 종류의 동전이 있다.
한 종류의 동전을 중복해서 여러개 사용할수 있다.
이 동전들로 K원을 만들려고 한다.
이때 동전의 개수를 최소화하고 그 수를 구하시오.
만약, K원을 만들수 없다면 -1을 제출하시오.

문제 패턴

최적해를 구하는 문제이다.
이전 상황을 이용해서 풀수있을것 같다.
쪼갤수 없는 냅색과 비슷한 부분이 있는것 같다.

어떻게 풀까? - 완전탐색

전체 경우의 수를 어떻게 구해야 할지 감이 잘 안 온다.
다양한 가치를 가진 동전의 조합을 K로 조율하는 과정부터 로직이 너무 복잡해질것 같다.

어떻게 풀까? - DP

포인트

각 가격별로 필요한 동전의 최소개수를 저장해서 이전 상태의 값으로 사용하자.
그러면 현재 X원 짜리 동전을 내서 K값을 만들때 K-X원 상태의 값을 사용해서 손쉽게 구할수 있다.

Ki = 1원부터 K원까지의 값. 1,2,3,4,5,6,...,K
AJ = 각 동전종류의 값어치. ex) 1,5,12, ..., An
dp[Ki][Aj] = 마지막으로 Aj를 내서 Ki가 될때, 필요한 동전의 최소개수.
dp[Ki][Aj] = dp[Ki-Aj][X]의 최소값 +1

코드

package study.week13;

import java.io.*;
import java.util.*;

public class BOJ_2294_동전2 {
	
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	// 세팅
	static int N;
	static int K;
	static int[] coins;
	static int[] minis;
	static int[][] dp;
	static int INF = Integer.MAX_VALUE;
	// 메서드
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		coins = new int[N];
		for (int i = 0; i < N; i++) {
			coins[i] = Integer.parseInt(input.readLine()); // 굳이 중복 없앨 필요 없음. 정렬할 필요도 없음.
		}
		// 세팅
		dp = new int[K+1][N]; 	// K값을 그대로 쓰기 위해서 0번 인덱스도 추가. 
								// 이렇게 하면 장점. 0번에 0의 값을 넣어두면, 
								// (Kj-Aj==0) 일때 DP[Ki-Aj][X]의 값이 항상 0이고 
								// 이때 +1을 하는 전체 로직으로 초기화를 함께 수행할수 있다.
								// 이 알고리즘은 도달불가능 표시와, 단 한번의 초기화(값을 채워나갈 기원점), 그리고 전체 로직으로 구성돼있다
		
		minis = new int[K+1]; 	// 각 가격별 최소 동전수를 저장하는 용도의 배열. 매번 dp의 행을 읽어도 되지만, 그냥 최적화 해봤음. 
								// dp테이블에 열 하나 추가해서 거기다가 넣어도 되지만, 뭔가 직관성 떨어져서 배열로 분리해서 만듬.
		// 작업
		for (int k = 0+1; k < K+1; k++) { 	// k=0일때인 dp[0][x]는 자동으로 0으로 초기화 된 상태.
			// int mini = INF;				// 행마다 추가로 저장되는 값과 mini값 비교해서 갱신하다가(그래서 당연하게도 for문 밖에서 선언.), 마지막에 최소값인 상태일때 minis에 저장하는 넣는용도.
											// 이렇게 하려다가. 복잡한것 같아서 직관성 위주로 코드를 전환. 행 완성했을때, 해당 행 한바퀴 돌면서 최소값 갱신해서 minis에 넣는 방식으로 전환.
			// 행 채우기.
			for (int i = 0; i < N; i++) {
				int Ai = coins[i];
				if(k-Ai<0) {
					dp[k][i] = INF; 		// 이전 상태가 -값이라면 현실에서 불가능한 상태 => 도달 불가능지점.
				} else{
					int preValue = minis[k-Ai];
					if(preValue==INF) {
						dp[k][i] = preValue;
					} else {
						dp[k][i] = minis[k-Ai]+1;
					}
				}
			}
			// 행의 최소값 구해서 저장하기.
			int mini = INF;
			for (int i = 0; i < N; i++) {
				int compare = dp[k][i];
				mini = Math.min(mini, compare);
			}
			minis[k] = mini;
		}
		// 출력
		if(minis[K]==INF) {
			System.out.println(-1);
		} else {
			System.out.println(minis[K]);
		}
		
	}// 메인 종료
}

숏코드

package study.week13;

import java.io.*;
import java.util.*;

public class BOJ_2294_동전2 {
	
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	// 세팅
	static int N;
	static int K;
	static int[] coins;
	static int[] minis;
	static int[][] dp;
	static int INF = Integer.MAX_VALUE;
	// 메서드
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		coins = new int[N];
		for (int i = 0; i < N; i++) {
			coins[i] = Integer.parseInt(input.readLine());
		}
		// 세팅
		dp = new int[K+1][N];
		minis = new int[K+1];
		// 작업
		for (int k = 0+1; k < K+1; k++) { 	
			for (int i = 0; i < N; i++) {
				if(k-coins[i]<0 || minis[k-coins[i]] ==INF) 
					dp[k][i] = INF;
				else
					dp[k][i] = minis[k-coins[i]]+1;
			}
			int mini = INF;
			for (int i = 0; i < N; i++) {
				mini = Math.min(mini, dp[k][i]);
			}
			minis[k] = mini;
		}
		// 출력
		if(minis[K]==INF) 
			System.out.println(-1);
		else 
			System.out.println(minis[K]);
		
	}// 메인 종료
}

퍼포먼스

[ 16,464KB | 96ms ]

마무리

DP는 항상 최적의 상태를 유지한다. 연쇄적으로.
이전 상태는 최적의 상태로 유지되고.
따라서 다음 상태도 최적이 된다는 점이 포인트이다.
어떤 점 B을 구할때, 그 점이 어떤 점들(Ai)에서 와가지고 B에 모이는 것인지 생각하면 편하다.
B는 어떤 Ai들로부터 오는것인지 파악하면, Ai에서 최선의 값을 골라서 B에 사용해주면 되는 것이다.

역시 숏코드는 별로다.
의미있는 변수명으로 바꿔주는 중간단계를 가져가면서 논리의 가독성을 챙기는게 좋다.