백준 21356 자바 - Hundraelva kronor (BOJ 21356 JAVA)

문제 : boj21356

 

 

  간단한 그리디 문제이다. 최소의 지폐 수를 구해야 하므로, 큰 값을 가지는 지폐부터 나누어나가면 된다. 문제의 제한에 맞는 1로 만들 수 있는 가장 큰 수부터 (111,111,111) n이 0이 될 때까지 한 자리씩 줄여나가면서(111,111,111 -> 11,111,111 -> 1,111,111 -> ... -> 1) 나눈 몫이 결국 출력해야 하는 지폐의 수이다. 그리고 매번 남은 나머지가 남은 지폐의 양이 된다. 결국 최종적으로는 1로 나누게 되므로 답을 못구하는 경우는 없다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int base = 111111111;
        int answer = 0;
        while (base!=0 && n!=0) {
            while (base > n) base/=10;
            answer += n/base;
            n%=base;
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}