[백준] 11047 동전 0 - Greedy / Java

• 문제 링크

11047번: 동전 0

 

• 풀이 과정

문제 중 동전의 가치가 일정한 값으로써 Ai가 Ai-1의 배수인 조건에 의해 그리디로 해결 가능하다.

 

동전은 n 종류, 가치의 합이 될 값은 k로 입력받고 각 동전의 가치가 오름차순으로 List에 저장된다.

우선 동전의 가치가 큰 순서대로 비교하기 위해 입력받은 List를 Collections.reverseOrder() 로 내림차순 정렬한다.

 

저장된 각 값을 k와 연산하는 반복문이 돌며 k값보다 작은 값으로 나눈 몫이 구해져 cnt 변수에 더해지고

나머지를 k값에 갱신해 반복문을 이어가 총 필요한 동전의 개수를 구한다.

 

• 풀이 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

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

		int n = sc.nextInt();
		int k = sc.nextInt();

		List<Integer> vals = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			vals.add(sc.nextInt());
		}
		vals.sort(Collections.reverseOrder());

		sc.close();

		int cnt = 0;
		for (int i = 0; i < n; i++) {
			int s = vals.get(i);
			cnt += k / s;
			k = k % s;
		}
        
		System.out.println(cnt);	
	}
    
}

 

이 방법 외에 List가 아닌 일반 배열을 두번째 반복문을 역순으로 비교해 정답을 구할 수 있다.

import java.util.Scanner;

public class Main {

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

		int n = sc.nextInt();
		int k = sc.nextInt();

		int[] vals = new int[n];

		for (int i = 0; i < n; i++) {
			vals[i] = sc.nextInt();
		}

		sc.close();

		int cnt = 0;
		for (int i = n - 1; i >= 0; i--) {
			int s = vals[i];
			cnt += k / s;
			k = k % s;
		}
        
		System.out.println(cnt);
	}
    
}