[Java] 백준 11047번 : 동전 0

문제

해결방법

• 이 문제의 입력 조건을 잘 보면, 동전 가치 배열인 A의 첫 번째 요소는 무조건 1이다
• 그 말은 어떠한 값이 와도 무조건 해결 가능하다는 것이다 !
  => 따라서, Greedy 기법을 이용하여 가장 큰 동전 값부터 빼면서 확인했다

코드

package com.ssafy.sejin;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * <pre>
 * 백준 11047. 동전
 * N개의 동전으로 K원을 맞추기 위한 최소값을 구하는 문제
 * 문제의 조건에 첫 번째 동전은 1원이기 때문에, 무조건 해결 가능한 문제임.
 * 그래서 Greedy방식을 통해 큰 동전부터 K에서 빼나가면서 K가 0이 될 때까지 반복하였음.
 * </pre>
 * @author 세진
 *
 */
public class BJ_11047_동전_천세진 {

	public static void main(String[] args) throws IOException {
		
		// 1. 사용자 입력 받기위한 객체들 생성
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 2. StringTokenizer와 parseInt 이용하여 n과 k 저장
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		// 3. 동전의 값을 저장하기 위한 n 크기의 coins 배열 선언
		int[] coins = new int[n];
		
		// 4. n번 반복하며 coins에 동전 값 저장
		for (int i = 0; i < n; i++) {
			coins[i] = Integer.parseInt(br.readLine());
		}
		
		// 5. 횟수를 저장하기 위한 answer 변수 선언
		int answer = 0;
		
		// 6. k를 감소시키며 while문을 도는데, 0이 되면 반복문을 빠져나옴
		while (k > 0) {
			
			// 7. coins의 제일 큰 index부터 1씩 줄이면서 k에서 해당 동전으로 나눈 나머지를 남김
			n--;
			
			// 8. answer에 k에 몇 개의 동전이 들어갔는지 추가
			answer += k / coins[n];
			
			// 9. 동전이 다 들어가고 나서, 남은 금액 (나머지)를 k에 저장
			k = k % coins[n];
			
			// 10. 만약 k가 0이라면, answer를 출력하고 return
            // (이 while문은 무조건 k가 0을 만족하는 시점이 오기 때문에 return값이 항상 존재)
			if (k == 0) {
				System.out.println(answer);
				return ;
			}
			
		}
		
	}

}