[BaekJoon] #11047 동전0

문제이해

이 문제는 동전의 종류가 N종류라고 할 때, 동전들을 이용해 동전들의 합으로 특정 입력으로 주어진 가치를 만들어야 합니다. 이때, 특정 값을 만들기 위해 필요한 동전갯수의 최소값을 만드는 문제입니다.

입력

입력으로 N과 K가 주어지고, 그 다음으로는 동전의 가치가 오름차순으로 주어집니다.

출력

출력으로는 k원을 만드는데 필요한 동전개수의 최솟값을 출력해야합니다.

---

문제접근

입력값 파싱 및 저장

• 입력을 위해 BufferedReader를 이용해주었습니다.
• N과 K를 분리해주기 위해 StringTokenizer를 이용해주었습니다.
• 계산에 필요한 동전의 가치는 배열로 관리해주어 각 동전을 정수형의 배열 arr에 저장해주었습니다.
• 이때, arr안에는 동전의 가치가 오름차순으로 정의되어있습니다.

solutions

• 문제해결에 필요한 함수 solution을 정의해주었습니다. 이 함수는 파라미터값으로 배열과 정수를 입력받습니다.
• 동전의 갯수가 최소가 되려면, 입력값을 나눌 수 있는 가장 큰 가치의 동전으로나누어야 합니다. 나눗셈의 결과로 도출되는 몫은 특정 가치에 해당하는 동전의 갯수를 의미합니다.
• 나눈 이후 나머지 값이 존재한다면, 이 값 또한 나눌 수 있는 가장 큰 가치의 동전으로 나누어야 합니다.
• 배열은 오름차순으로 정렬되어 있기 때문에 for문을 이용해주어 배열의 마지막 인덱스부터 접근해주어 나눗셈연산과 나머지연산을 이용해 연산 후, 동전의 갯수를 의미하는 count값을 누적하여 더해주었고, K를 업데이트해주는 코드를 작성해주었습니다.

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

code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

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 K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        for(int i= 0; i< N ; i++){
            arr[i] =Integer.parseInt(br.readLine());
        }
        int ans = solution(arr,K);
        System.out.println(ans);

    }

    private static int solution(int arr[], int K){
        int count = 0;
        for(int i =arr.length-1; i>=0; i--){
            if( arr[i] <= K ){
                count +=  K/arr[i];
                K = K %arr[i];
            }
        }
        return count;

    }
}

결과화면