[백준] 동전 0 11047번 - Java

[백준] 동전 0 11047번

나의 풀이

public class Coin {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int K = Integer.parseInt(s[1]);
        int answer = 0;
        Integer[] coins = new Integer[N];

        for(int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        for(int i = N - 1; i > -1; i--) {
            if(coins[i] > K) continue;
            answer += K / coins[i];
            K %= coins[i];
            if(K < 1) break;
        }

        System.out.println(answer);
    }
}

• N, K를 입력받고 N만큼 coins 배열에 동전의 종류를 넣어준다.
• 문제에 오름차순으로만 입력된다는 조건이 있기 때문에 이번에는 정렬을 하지 않았다. 동전의 최소개수를 구하려면 큰 동전부터 계산을 해나가야 하기 때문에, coins 배열의 뒤에서부터 계산을 진행하였다. 정렬을 따로 하지 않았는데 속도측면에서는 정렬하는거랑 차이가 없었다.
• 동전의 종류가 K보다 크다면 continue 를 하고, 아니라면 계산을 해준다. i번째 동전으로 지불할 수 있는 최대한의 개수를 answer 에 더해주고, K 는 지불한 만큼 차감해준다. 동전의 종류는 1이 최소이기 때문에 K가 1보다 작아질 경우 계산이 불가능하다. 따라서 K가 1 미만이 된다면 반복을 종료하고 answer 를 출력해준다.