[자바 JAVA/알고리즘]백준 11047번 : 동전 0

GitHub https://github.com/vellimole0621

 

백준 11047번 : 동전 0

 

(문제 -https://www.acmicpc.net/problem/11047 )

 

문제 설명 :   준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

풀이 :

(*아이디어 : 최솟값을 만들기 위해서는 큰 값의 동전 종류부터 빼본다.)

동전 N 종류 와 목표값 K를 입력 받음 -> 1부터 10000까지 동전 종류 입력 받음 -> 동전 종류는 정수형 배열에 집어 넣는다. -> 반복문으로 제일 큰 동전부터, 동전의 값보다 K가 클 경우 빼는 방식으로 동전의 개수를 더한다. -> K의 값이 0이 되면, 그 때의 동전 개수를 출력한다.

 

//백준 11047번 : 동전 0
// https://www.acmicpc.net/problem/11047

import java.util.Scanner;
public class CoinAlgorithm {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// n과 k 값 받기
        int n = sc.nextInt();
        int k = sc.nextInt();

        // 동전 종류 담을 배열 선언
        int[] coinArray = new int[n];

        // 동전 종류 입력
        for(int i = 0; i < n; i++){
            coinArray[i] = sc.nextInt();
        }

        // 중간 변수 선언
        int temp = 0;

        for(int j = n-1; j >= 0; j--){
            if(k >= coinArray[j]){
                temp = temp + (int)Math.floor(k/coinArray[j]);
                k = k - (int)Math.floor(k/coinArray[j]) * coinArray[j]; 
        }
        if(k == 0){
            break;
        }
        }

        System.out.println(temp);
		sc.close();

	}
}

 

피드백

:

아이디어 자체는 빠르게 생각해냈는데, 소수점 처리에서 시간이 걸렸다. '동전의 종류별로 몇개를 빼야하는가?'에서 현재 값 / 현재 동전 종류를 통해 계산하는 방식을 사용했는데, double 형태로 값이 처리되어 이걸 int로 바꾸는 과정에서 round에서 floor로 갔다가 (int)까지 가는 과정에서 시간이 걸렸다.

 

Math. floor ceil round 처리가 핵심인 문제였다.