[Java] ❤동전교환

import java.util.*;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE-1);
        dp[0] = 0;

        for (int i = 0; i <= dp.length; i++) {
            for(int coin : coins) {
                if(i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] ==Integer.MAX_VALUE-1 ? -1 : dp[amount];
    }
}

문제 설명

여러 종류의 동전을 나타내는 정수 배열 coins가 주어집니다. 또한, amount라는 총 금액이 주어집니다.

이 금액을 만들기 위해 필요한 최소 동전의 수를 반환하세요. 만약 이 금액을 주어진 동전으로 만들 수 없다면 -1을 반환하세요.

각 동전의 개수는 무한히 많다고 가정할 수 있습니다.

주석ver.

import java.util.*;
class Solution {
    public int solution(int[] coins, int amount) {
        // dp 배열을 생성하고, 모든 값들을 Integer.MAX_VALUE-1로 초기화합니다.
        // dp[0]은 0으로 설정합니다. (0원을 만들기 위해 필요한 동전의 개수는 0개입니다.)
        int[] dp = new int[amount + 1];
        int INF = Integer.MAX_VALUE - 1;  // 무한대를 나타내기 위한 값입니다.
        Arrays.fill(dp, INF);  // 모든 dp 값을 무한대 값으로 초기화합니다.
        dp[0] = 0;  // 0원을 만들기 위해 필요한 동전 개수는 0개입니다.
        
        // dp 배열을 업데이트 하기 위해 모든 금액을 고려합니다.
        for (int i = 0; i < dp.length; i++) {
            // 각 동전을 반복하여 현재 금액 i를 만들 수 있는지 확인합니다.
            for (int coin : coins) {
                // 현재 금액 i가 동전의 가치 이상인 경우
                if (i >= coin) {
                    // dp[i]를 갱신하여 최소 동전 개수를 저장합니다.
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // 만약 dp[amount]가 무한대 값으로 남아있다면, 주어진 금액을 만들 수 없다는 의미입니다.
        // 그렇지 않다면 dp[amount]를 반환하여 최소 동전 개수를 출력합니다.
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

Q1. amount에 1을 더하는 이유

 int[] dp = new int[amount + 1];

A1.

amount + 1 길이의 dp 배열을 사용하는 이유는 이 배열이 금액을 표현하는 인덱스들을 포함하기 때문

인덱스와 금액의 대응 관계:

• 배열 dp의 인덱스 i는 i 금액을 만들기 위해 필요한 최소 동전 수를 의미한다.
• 예시) dp[0]은 0원을 만들기 위한 최소 동전 수, 즉 0개를 나타내고,

  dp[1]은 1원을 만들기 위한 최소 동전 수를 나타낸다.