[백준] 11047 : 동전 0

1. 문제

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

2. 문제 풀이

1) 문제풀이 아이디어 : 그리디 알고리즘

이 문제를 그리디 알고리즘을 이용하면 간단히 풀 수 있다.

그리디 알고리즘 : 매 번 선택에서 가장 좋아보이는 선택을 하여 적절한 답을 찾아간다.

화페 단위 큰거부터(가장 좋아보이는 선택) 먼저 하면 되겠네? 라는 생각을 얻었다.

<예제 1>

동전 종류 : 1원, 5원, 10원, 50원, 100원, 500원, 1000원, 5000원, 10000원, 50000원

목표 금액 : 4200원

최적해 : 1000원(4개) , 100원(2개) , 총 6개

<예제 2>

동전 종류 : 1원, 5원, 10원, 50원, 100원, 500원, 1000원, 5000원, 10000원, 50000원

목표 금액 : 4790

최적해 :

1000원 4개,

500원 1개,

100원 2개

50원 1개

10원 4개

총 4+1+2+1+4=5+3+4=12 , 12개

2) 이 문제를 그리디로 풀 수 있는 이유는?

화폐들이 서로 배수들의 관계이므로! 최적해를 만족한다!!

내가 문제를 그리디로 접근할 때 확인하는 기준이 있다.

1) 그리디 알고리즘으로 접근하는 것이 최적해를 만족하는 가?

2) 반례가 없는가?

이다.

문제 조건이 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우 Ai는 Ai-1의 배수) 이다.

동전들이 모두 배수 관계로 구성되어 있으므로, 큰 단위 화폐부터 사용하는 것이 최적해를 만족한다.

이 문제는 아니지만, 그리디가 통하지 않는 경우로는

동전의 종류 : 500원, 400원, 100원

목표금액 : 800원

1) 그리디 풀이 : 500원(1개) + 100원(3개) = 4개

2) 최적해 : 400원(2개) = 2개

-> 따라서 동전이 배수 관계가 아닐 경우, 그리디는 최적해를 보장하지 못한다.

3) 시간복잡도 분석

범위 : (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

주어지는 N과 K의 범위는 다음과 같다.

K는 총 만드려는 금액의 수 이므로 실질적으로 시간복잡도에 영향을 끼치진 않는다.

N이 실질적으로 시간복잡도에 영향을 주는 값인데, 최대 10개이기때문에 어떤 방식으로 풀던 영향을 줄 수 있을 정도는 아니다.

3. 코드

import java.util.*;
import java.io.*;

public class BOJ11047{
    public static void main(String[] args) throws IOException{
        int answer=0;
        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[] coins=new int[n];

        for(int i=0;i<n;i++){
            coins[i]=Integer.parseInt(br.readLine());
        }
        
        for(int i=n-1;i>=0;i--){
            answer+=k/coins[i];
            k%=coins[i];
        }

        System.out.println(answer);
    }
}

지우의 우당탕탕 개발일지

[백준] 11047 : 동전 0 - JAVA [자바]