[LeetCode] 322. Coin Change (java)

https://leetcode.com/problems/coin-change/

 

 

문제 파악

• 입력
  • coins: 동전의 종류를 담은 정수 배열
  • amount: 목표 금액
• 조건
  • 동전은 무한히 사용할 수 있음
• 출력
  • amount를 만들기 위해 필요한 최소 동전 개수 반환
  • 만들 수 없으면 -1 반환

 

 

문제 풀이

BFS

class Solution {
  
    public int coinChange(int[] coins, int amount) {
        Queue<Entry> queue = new LinkedList<>();
        boolean[] visited = new boolean[amount + 1];

        if (amount == 0) return 0;

        queue.add(new Entry(0, 0));
        while (!queue.isEmpty()) {
            Entry curr = queue.remove();

            for (int coin : coins) {
                int nextCoin = curr.amount + coin;

                if (nextCoin > amount) continue;

                if (nextCoin == amount) return curr.count + 1;

                if (!visited[nextCoin]) {
                    visited[nextCoin] = true;
                    queue.add(new Entry(nextCoin, curr.count + 1));
                }
            }
        }

        return -1;
    }

    class Entry {
        int amount;
        int count;

        Entry(int amount, int count) {
            this.amount = amount;
            this.count = count;
        }
    }
}

 

📊 실행 결과