[코드트리] 아이템을 적절히 고르는 문제 / 동전 거슬러주기

[코드트리]

문제 # https://www.codetree.ai/missions/2/problems/coin-change?utm_source=clipboard&utm_medium=text

 

 

내가 작성한 코드

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

public class Main {
    static final int INF = (int)1e9;
    static int N, M; // 동전 종류 수와 거슬러 줄 금액
    static int[] coins; // 동전 종류별 금액
    static int[] dp; // idx원을 거슬러 줄 때, 필요한 최소 동전의 수 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

// 초기화
        coins = new int[N]; 
        dp = new int[M+1]; 
        Arrays.fill(dp, INF);
        dp[0] = 0; // 0원을 거슬러 줄 때, 필요한 최소 동전의 수 = 0 

        st = new StringTokenizer(reader.readLine());
        for(int i=0; i<N; ++i){
            coins[i] = Integer.parseInt(st.nextToken());
        }  

        for(int i=1; i<=M; ++i){ // 1원부터 M원까지 
            for(int j=0; j<N; ++j){ // coins[0] ~ coins[N-1]까지 
                int prev = i - coins[j]; // i - coins[j] 원 => coins[j]원을 더하여 현재 금액을 만들기 전 
                if(prev < 0 || dp[prev] == INF) continue; // 이전 금액이 0원보다 적은 금액이거나, coins[j]원을 더하기 전인 이전 금액이 주어진 동전들로 만들 수 없었던 경우,
                dp[i] = Math.min(dp[i], dp[prev] + 1); 
            }
        }
        if(dp[M] == INF){ // 돈을 거슬러 주는 것이 불가능할 경우, 
            dp[M] = -1;
        }
        System.out.println(dp[M]);
    }
}

 

풀이 및 배운 점

 

처음 기본 예시에서는 최대 개수라 dp[] 배열을 Integer.MIN_VALUE로 초기화해줬는데, 해당 문제는 최소 개수라 Integer.MAX_VALUE로 초기화해줘야하는 문제였다. 이 부분을 생각하지 못하고, 무작정 -1로 초기화해주었더니 생각했던 알고리즘이 틀리지 않았는데도 불구하고 답이 나오지 않았다. 

 

무작정 코딩하는 것이 아니라, 해당 문제에서 구하고자 하는 것과 그것을 위한 초기화 등에 대한 생각을 할 필요가 있다는 것을 다시 한 번 느꼈다. 

 

보통 아닌 경우를 continue하여 컷하는 습관을 들이다보니, if문을 두 번 쓰거나 if문 하나에 조건 두 가지를 같이 적는 방법을 택해야했다.

이 때, if문 안에 i - coins[j] 를 두 번 작성해야하니, 가독성이 떨어지는 문제가 발생하였다.

가독성을 높이고 코드 작성을 간결하게 하고자 prev라는 int형 변수를 두어 coins[j]를 더하기 전 금액에 해당하는 값을 저장하는 방법을 생각했다.

 

변수 하나를 더 사용하는 방법을 생각해내는 과정겪으면서 짧은 시간이지만, 해당 알고리즘에 대한 이해가 조금 더 명확히 된 것 같다.