[백준/Java] 11047번 : 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

✔️ 풀이과정

그리디 알고리즘(Greedy Algorithm)의 가장 대표적인 문제이다.

그리디 알고리즘이란 각 단계에서 가장 최적인 것을 선택하는 알고리즘을 말하는데, 해당 알고리즘을 사용하기 위해서는 문제에서 이전의 선택이 이후의 선택에 영향을 주지 않는 독립적인 상태여야 하고, 최종적인 최적해가 부분 문제에 대한 최적해여야 한다.

처음 문제를 풀이했을 때 최적의 선택을 위해 가지고 있는 동전 중 K보다 작지만 K와 가장 가까운 동전을 고른 뒤, count 변수를 선언하여 동전 개수를 카운트 하고, 뺄셈 연산 기호를 사용하여 남은 거스름돈을 구하는 식으로 해를 구할 때까지 반복하려고 하였다. 하지만 생각보다 코드가 길어져 다른 문제 풀이 방법을 찾아보았고, 나눗셈 연산자를 사용하여  count 값을 구하고, 나머지 연산자를 사용하여 거스름 돈을 구하는 방식의 매우 간결한 풀이법을 알게 되었다. 코드는 다음과 같고, 참고 출처 사이트는 아래에 기재해두었다.

 

✔️ 코드

import java.io.*;
import java.util.*;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    int []coin = new int[N];

    for (int i=0;i<+N;i++){
      st = new StringTokenizer(br.readLine());
      coin[i] = Integer.parseInt(st.nextToken());
    }

    int count = 0;
    for (int i=N-1 ; i>=0 ; i--){
      if (coin[i] <= K){
        count += (K / coin[i]);
        K = K % coin[i];
      }
    }

    bw.write(Integer.toString(count));
    bw.flush();
    bw.close();
  }
}

 

✔️ 참고 사이트

https://st-lab.tistory.com/143