[알고리즘풀이]백준 11047: 동전 0 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 11047번 동전 0을 풀었습니다. 이를 정리해보고자 합니다.

11047번: 동전 0

 

본문

1) 문제

 

2) 과정

처음 풀어본 greedy 유형의 문제였습니다. 

그래선지 낯설었지만 어렵진 않게 풀었던 것 같습니다.

 

2-1) main

    // Attribute
    private static int n,k;
    private static Integer[] pocket;
    private static Integer[] counter;
    
    private static ArrayList<Integer> list;
    private static int listSize;
    
    // Main
    public static void main(String[] args) throws IOException {
        input();
        func();
    }

main은 다음과 같습니다. input과 func로 구성하였습니다. 각각은 아래 나올 내용의 Input, Logic입니다.

그리고 사용할 변수를 전역변수로 선언해줍니다.

n, k는 각각은 입력 받았던 동전의 종류 수 N, 만들고자하는 값 K입니다.

 

2-2) Input

   public static void input() throws IOException {
   	// Input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr = reader.readLine().split(" ");
        n=Integer.parseInt(strArr[0]);
        k=Integer.parseInt(strArr[1]);

        list = new ArrayList<Integer>();
        for(int i =0;i<n;i++) {
            int tmp = Integer.parseInt(reader.readLine());
            if(k>=tmp) list.add(tmp);
            else break;
        }
        
        // Initialize
        list.sort(Comparator.reverseOrder());
        listSize=list.size();
    }

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

첫번째 줄을 읽어 n과 k에 값을 넣어줍니다. 이후 k보다 큰 수는 계산에 사용되지 않을 수이기 때문에  n번 반복하며 k보다 작은 수만 읽어 list에 담습니다. 

 

Initialize 과정으로 list를 역순으로 정렬(큰수 -> 작은 수 순으로) 해주고 자주 사용될 list의 크기는 listSize에 담아둡니다.

 

2-3) Logic

    private static void func(){
        int remain = k;
        int coin = 0;
        for (int i = 0; i < listSize ; i++) {
            coin += remain/list.get(i);
            remain %= list.get(i);
        }
        System.out.println(coin);
    }

func()를 불러줍니다. 지역변수 remain은 남은 금액을 의미하고, coin은 사용된 동전의 수이자 정답을 의미합니다.

for문으로 큰 수부터 읽어 가장 큰 값을 coin에 최대한 더하고 남은 금액을 %=을 통해 remain에 넣습니다.

모든 과정을 마친 뒤 coin을 출력하며 실행은 종료됩니다.

 

예를 들어 설명하면, 5000원 3000원 1000원이 있을 때 k가 9000원이라면,

첫 for문에선 9000/5000의 몫인 1이 coin에 더해지고 remain은 나머지 4000이 됩니다.

그 다음 for문에선 4000/3000의 몫인 1이 coin에 더해지고 remain은 나머지 1000이 됩니다.

그 다음 for문에선 1000/1000의 몫인 1이 coin에 더해지고 remain은 0이 됩니다.

이제 모든 동전의 종류를 다 돌았으니, coin의 값인 3을 출력하고 종료합니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class BOJ11047 {

    private static int n,k;

    private static ArrayList<Integer> list;
    private static Integer[] pocket;
    private static Integer[] counter;
    private static int listSize;

    public static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr = reader.readLine().split(" ");
        n=Integer.parseInt(strArr[0]);
        k=Integer.parseInt(strArr[1]);

        list = new ArrayList<Integer>();
        for(int i =0;i<n;i++) {
            int tmp = Integer.parseInt(reader.readLine());
            if(k>=tmp) list.add(tmp);
            else break;
        }
        list.sort(Comparator.reverseOrder());
        listSize=list.size();
    }

    private static void func(){
        int remain = k;
        int coin = 0;
        for (int i = 0; i < listSize ; i++) {
            coin += remain/list.get(i);
            remain %= list.get(i);
        }
        System.out.println(coin);
    }

    public static void main(String[] args) throws IOException {
        input();
        func();
    }
}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/greedy/BOJ11047.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비