코드업(Codeup) 2634 : 거스름돈 II

import java.util.Scanner;
import java.util.List;
import java.util.Vector;

public class Main {	
    static int[] coins;
    static List<Integer> rs2_arr = new Vector<>();

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

        int price = sc.nextInt();
        int cnt = sc.nextInt();
        coins = new int[cnt];
        for(int i = 0; i < cnt; i++) {
            coins[i] = sc.nextInt();
        }

        int loopCnt = cnt - 1;

        int rs1 = 0;
        int rs2 = 0;

        for(int i = cnt - 1; i >= 0; i--) {
            if(price % coins[i] == 0) {
                rs1 = price / coins[i];
                break;
            }
        }

        OtherSolution(price, loopCnt, rs2, false);
        rs2 = rs2_arr.get(0) < rs2_arr.get(1) ? rs2_arr.get(0) : rs2_arr.get(1);

        System.out.println(rs1 < rs2 ? rs1 : rs2);
    }

    static void OtherSolution(int price, int loopCnt, int rs, Boolean isLoop) {
        while(price > 0){
            if(price / coins[loopCnt] >= 1) {
                if((int)(price / coins[loopCnt]) == 1 && !isLoop) {
                    isLoop = !isLoop;
                    OtherSolution(price, loopCnt - 1, rs, isLoop);
                }

                price -= coins[loopCnt];
                rs++;
            }
            else {
                loopCnt--;
            }
        }

        rs2_arr.add(rs);
    }
}