[백준] 단계별로 풀어보기(단계:16,그리디 알고리즘,JAVA)11047번, 동전 0

문제 링크

11047번: 동전 0

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그리드 알고리즘(탐욕 알고리즘)이란 여러 경우를 선택해야할 때 그 상황에 최적의 경우으로 생각하는 것을 반복하여 최종적인 답을 가져오는 방법입니다.

 

이 문제에서는 동전의 최소의 개수를 얻으려면 가치가 큰 동전을 최우선 사용하여 동전의 최대 가치를 0을 만들어야 합니다.

문제에서 입력에서 동전의 가치가 오름차순으로 정렬되어 있기 때문에 정렬하지 않아도 됩니다.

가치가 높은 동전순으로 최대값을 나누어서 몇개의 동전이 사용되는지 파악하고 나머지를 다음 가치가 높은 동전으로 나누는 과정을 반복하여 최소값을 구하도록 알고리즘을 설계하였습니다.

 

• 입력받은 코인의 가치를 저장할 배열 coin를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 띄어쓰기로 나누어 동전의 개수와 최대 최대 가치를 저장하였습니다.
• 동전의 최소 사용 개수를 계산하는함수 coinZero을 만들었습니다.
• BufferedWriter을 사용하여 최소값을 출력하였습니다.

• 가치가 높은 동전부터 나누어 개수를 파악하고 나머지를 다음 가치인 동전으로 나누는 것을 반복하였습니다.
• 최대 가치가 0이 되었다는 것은 더이상 나눌 수 없기 때문에 break문을 사용하여 반복을 중단하였습니다.
• for문이 종료되면 최소값을 반환하도록 하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] coin;	//동전 저장 배열
	static int maxValue;	//최대 값
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //------입력값 저장 및 배열 초기화----------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int index = Integer.parseInt(st.nextToken());
    	maxValue = Integer.parseInt(st.nextToken());
    	coin = new int[index];
    	for(int i=0;i<index;i++) 
    		coin[i] = Integer.parseInt(br.readLine());

    	bw.write(coinZero(index) + "\n");	//함수 결과 출력
    	bw.flush();
    	bw.close();
    	br.close();
	}
    //-----------동전 0이 되는 최소값 구하는 함수------
	public static int coinZero(int index) {
		int result=0;
		for(int i=index-1;i>=0;i--) {
			if(maxValue==0)
				break;
			else {
				result += maxValue/coin[i];
				maxValue = maxValue%coin[i];
			}
		}
		return result;
	}
}