그리디 - 백준11047 동전 0

그리디

• 각 단계에서 최적이라고 생각되는 것을 선택해나가는 것
• 그리디 문제 푸는 방법 : 같은 건 따로 없음, 그냥 iq테스트
• 풀이가 틀렸을 경우 오래 붙잡혀있을 가능성 높은 유형
• 코딩테스트에서의 추천 전략
  거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다 -> 짜서 제출해보고 틀리면 빠르게 손절
  100%확신은 없지만 풀이를 찾았다 -> 일단 넘어가고 마지막에 시도
  출처 https://www.youtube.com/watch?v=De0Qg-2O80c&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=18

문제풀이
실버4문제이고, 그냥 문제를 보면 어떻게 푸는지 알 수 있다.
문제를 요약하면, 주어진 값을 지불하기 위해 동전을 최소로 사용하는 경우의 동전 갯수 구하기다.
따라서 단위가 큰 동전부터 사용해 보면 된다.

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n,k;
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int[] coins = new int[n];
        for(int i = 0; i < n; i++){
            coins[i] = Integer.parseInt(br.readLine());
        }
        int left = k;
        int answer = 0;
        for(int i = 0; i < n; i++){
            int nowCoin = coins[n-i-1];
            //나누고 사용한 동전 갯수 저장, 남은 나머지 저장
            answer += left/nowCoin;
            left %= nowCoin;
        }
        System.out.println(answer);
    }
}

처음으로 문제를 1분만에 풀었다.