백준 11047번: 동전 0

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

N종류의 동전을 가지고 가장 적은 수의 동전으로 K값을 정확히 만들어내는 문제이다.

 

어떤 값을 만들 때 그것보다 가장 작은 값 중의 가장 큰 값을 찾아야 했다.

이전에 TreeMap을 사용하면서 higher, lower에 관한 메소드가 있던 것으로 기억해서 TreeSet을 찾아봤다.

생각대로 TreeSet에 higher, lower 메소드가 있었고 그걸 이용해서

입력받은 K값의 나머지가 0가 될 때 까지 반복문을 돌리면서 가장 적은 수로 K를 만드는 법을 찾았다.

 

그렇게 만들고 몇 번 실행해봤을 때 내가 관과한 사실이 있다는 것을 깨달았는데,

바로 값K가 동전의 값과 일치할 때를 고려하지 않았다는 것이다.

(예를 들면 100원 동전이 있는데 100을 입력받은 경우)

lower 메소드는 입력받은 값보다 미만의 값 중 최대값을 골라주기 때문에 문제가 발생했다.

그래서 contains 메소드로  K값이 TreeSet에 포함되는지 확인하고

만약 그렇다면 반복문을 통과하고, 동전의 수를 1증가하도록 만들어주어 문제를 풀 수 있었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.TreeSet;

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 = Integer.parseInt(st.nextToken());
    int value = Integer.parseInt(st.nextToken());
    TreeSet<Integer> ts = new TreeSet<>();
    int ctr = 0;

    for (int i = 0; i < N; i++) 
      ts.add(Integer.parseInt(br.readLine()));
    br.close();

    while (value > 0) {
      if (ts.contains(value)) {
        value %= value;
        ctr++;
      }
      else {
        ctr += value / ts.lower(value);
        value %= ts.lower(value);
      }
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write( ctr + "\n");
    bw.flush();
    bw.close(); 
  }
}