백준 - 동전0

문제 출처:www.acmicpc.net/problem/11047

11047번: 동전 0

풀이

다행스럽게도 입력되는 금액의 가치들이 오름차순으로 입력된다. 굳이 정렬을 해줄 필요가 없다.

큰 가치부터 내림차순으로 내려오면서 K랑 나눴을 때 몫이 0보다 크면, 몫을 계속 ans변수에 더해줬다.

그리고 K는 나머지로 바꿔주면서 쭉 진행하면 정답이 나온다.

코드

	package algorithm;
	import java.util.Scanner;
	public class B11047_동전0 {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int K = sc.nextInt();
	int ans = 0;
	int coins[] = new int[N];
	for (int i = 0; i < N; i++) {
	coins[i] = sc.nextInt();
	}
	for (int i = coins.length - 1; i >= 0; i--) {
	int divided = coins[i];
	if (K / divided > 0) {
	ans += (K / divided);
	K = K % divided;
	}
	}
	System.out.println(ans);
	}
	}

view raw 동전0 hosted with ❤ by GitHub