[백준 2024/01/20] 11047번 동전 0

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

11047번: 동전 0

 

1. 접근 방법

이전에 동전과 관련된 문제를 푼 적이 있다.

당시엔 동전의 개수가 random이지 않았고, 500원 1000원 이런식으로 정해져 있던 것으로 생각이든다.

 

하지만, 이번 문제는 동전의 가치가 많았다.

1원이 있다는 점이 이 문제를 접근하기 쉽게 만들었다.

 

1원이 있다는 뜻은, 동전의 가치가 큰 것부터 나누기를 해나가며, 남은 부분을 1원으로 채우면 된다는 뜻이다.

이 부분을 깨닫고 난 후엔 쉽게 다가갈 수 있었다.

 

k원에 대해서 가치가 큰 동전으로 나눠나갔으며, 만약 몫이 0이라면 skip해주었다.

몫이 0이 아니라면 그 몫을 result에 저장해두고, 몫*동전의 가치를 k에서 빼주었다.

rough draft

 

2. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class b11047 {
    public static void main(String[] args) throws IOException {

        List<Integer> list = new ArrayList<>();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();
        String[] num = line.split("\\s+");
        int n = Integer.parseInt(num[0]);
        int k = Integer.parseInt(num[1]);

        for(int i =0; i<n;i++){
            list.add(0,Integer.parseInt(reader.readLine()));
        }

        System.out.println(sum(list, k));

    }

    public static int sum(List<Integer> list, int k){
        int result = 0;

        int quotient;
        for(int i=0; i<list.size(); i++) {
            if ((k / list.get(i) != 0) ) {
                quotient = k/list.get(i);
                result += quotient;
                k -= list.get(i)*quotient;
            }
        }
        return result;
    }

}