[java]동전 0 - 백준11047

문제

• 동전(백준11047)

풀이

문제 해석을 하자면,

• 준규가 가지고 있는 동전은 총 N종류
• 동전을 적절히 사용해서 그 가치의 합을 K로 만들때 필요한 동전 개수의 최솟값을 구하라

풀이

• 돈전 거스름돈 문제이다 -> DP 유형으로 유명
• 그러나 이 문제는 Ai 가 Ai-1 의 배수이므로 “그리디” 로 풀 수 있는 문제이다.
  • 풀이 : 입력이 오름차순으로 주어지므로 반대로 for 문 조회하면서 “큰 값 부터 가능한 만큼 동전 사용”

코드

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    int N = Integer.parseInt(stk.nextToken());
    int K = Integer.parseInt(stk.nextToken());
    int[] inArr = new int[N + 1];
    for (int i = 0; i < N; i++) {
        inArr[i] = Integer.parseInt(br.readLine());
    }
    //run
    int sum = 0;
    int result = 0; // count
    for (int i = N - 1; i >= 0; i--) {
        int diff = K-sum;
        if (inArr[i] <= diff) {
            while (inArr[i] <= diff) { // inArr[i] 값을 더할 수 있는 최대만큼 반복해서 더한다.
                sum+=inArr[i];
                diff = K-sum; //update
                result++; //update
            }
        }
    }
    //output
    System.out.println(result);
}

느낀점

생략