[프로그래머스] 동전 교환

 

 

문제 파악

-dp활용

 

 

제한 사항

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

접근 방법

-0~n까지 현재 금액 누적해가기(for문)

-금액 도달 전까지 누적해가며 dp 수행, 수행하면서 대상 값을 업데이트해가며 돌려줌(amount-coin)

-완전탐색으로도 구현이 가능하나 효율성에서 문제 발생!!

-메모이제이션 활용) n번째 계단처럼, n번째 값까지의 최소값을 하나하나 메모해두고

계산하지 않은 것만 dp수행, 이미 계산된 것은 배열 안에서 골라서 result값 갱신하기

코드 구현

import java.util.*;
class Solution {
    public int solution(int[] coins, int amount) {
        int[] memory = new int[amount+1];
        Arrays.fill(memory,Integer.MAX_VALUE);
        int answer=dp(coins,amount,memory);
        return answer==Integer.MAX_VALUE?-1:answer;
    }
    public int dp(int[] coins, int amount,int[] memory){
        int result = Integer.MAX_VALUE;
        if(amount==0) return 0;
        for(int coin:coins){
            if(amount-coin>=0){
                if(memory[amount-coin]==Integer.MAX_VALUE){//연산안한 경우
                    memory[amount-coin] = dp(coins,amount-coin,memory);//메모해두기
                }
                result = Math.min(result,memory[amount-coin]);//기억된 것 활용해서 값 계산
            }
            // if(amount-coin>=0){//완전탐색
            //     result = Math.min(result,dp(coins,amount-coin));
            // }
        }
        return result==Integer.MAX_VALUE?result:result+1;
    }
}

 

 

 

dp는 memorization 전법!