공부 101일차: 백준 11047번 동전 0 자바 java

11047 동전 0

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

11047번: 동전 0

 

 

 

---

백준 11047번 문제 동전 0

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

1. 동전개수 n과 구해야 하는 금액 k를 받는다

2. n개만큼 주어진 동전 단위들을 모두 배열에 저장한다

3. 동전 개수가 최소 = 가장 큰 단위부터 사용하는 것이므로, 배열의 가장 큰 값부터 k에서 뺄 수 있는 만큼 뺀 후 다음으로 큰 단위 숫자로 넘어간다

 

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] coin = new int[n];
        
        for(int i = 0; i < coin.length; i++) {
            st = new StringTokenizer(br.readLine());
            coin[i] = Integer.parseInt(st.nextToken());
        }
        
        int count = 0;
        for(int i = n-1; i >= 0; i--) {    //가장 큰값부터 거꾸로
            if(k >= coin[i]) {    //k가 i번째 동전단위보다 크다면
                while(true) {
                    k -= coin[i];    //계속 i번째 동전단위만큼 뺀다
                    count++;
                    if(k < coin[i])    //k가 i번째 동전단위보다 작아졌다면
                        break;    //while문만 탈출 -> 그다음작은 단위로 넘어감
                }
                /* while문 대신
                 * 
                 * count += k/coin[i];
                 * k = k%coin[i];
                 * 
                 * 도 가능*/
            }
        }
        System.out.println(count);
    }
 
}
 

 

위의 설명과 주석을 통해 이해할 수 있으리라 생각한다

굉장히 쉬웠던 문제..

 

찾아보니 반복문을 사용하지 않고 몫과 나머지를 이용하는 사람들도 많았다

(/**/ 주석처리한 부분)

 

 

 

---

그리디 알고리즘 단계에 나와있는 문제

현재 그리드 알고리즘의 최종 목표 문제인 18768번 팀 배정을 풀기 전에 한 번 해봤다