[문제풀이] 10-05. 동전 교환

인프런, 자바(Java) 알고리즘 문제풀이

Dynamic Programming - 1005. 동전 교환(냅색 알고리즘)

🗒️ 문제

🎈 나의 풀이

	private static int solution(int[] coins, int change) {
       int[] dy = new int[change + 1];

       for(int i=0; i<=change; i++) dy[i] = i;

       for(int i=1; i<coins.length; i++) {
           int coin = coins[i];

           for(int j=coin; j<=change; j++) {
               dy[j] = Math.min(dy[j], dy[j-coin] + 1);
           }
       }

       return dy[change];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] coins = new int[n];

        for(int i=0; i<n; i++) coins[i] = sc.nextInt();

        int change = sc.nextInt();
        System.out.println(solution(coins, change));
    }

🖍️ 강의 풀이

  	static int n, m;
	static int[] dy;
	public int solution(int[] coin){
		Arrays.fill(dy, Integer.MAX_VALUE);
		dy[0]=0;
		for(int i=0; i<n; i++){
			for(int j=coin[i]; j<=m; j++){
				dy[j]=Math.min(dy[j], dy[j-coin[i]]+1);
			}
		}
		return dy[m];
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
		}
		m=kb.nextInt();
		dy=new int[m+1];
		System.out.print(T.solution(arr));
	}

💬 짚어가기

해당 문제는 그래프의 Dynamic Programming(동적 계획법)을 통해 풀 수 있다.
그 중 냅색(knapsack) 알고리즘을 이용하여 풀이하였다.

거스름돈 크기만큼의 배열 dy를 생성한다. 해당 배열의 인덱스는 금액을 의미한다.
그 다음 동전 종류 별로 dy 배열을 순회하며 dy 배열을 업데이트한다.

dy[j]=Math.min(dy[j], dy[j-coin[i]]+1)

동전의 크기를 coin[i]라고 했을 때,현재 금액 j를 만들기 위해 이전 동전까지의
최소 동전 개수와 현재 동전을 사용한 경우를 비교하여 최소값을 선택합니다.