백준 11047번 자바 : 동전 0

백준 11047번

11047번: 동전 0

 

문제

---

 

풀이

---

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

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int cnt = 0;
        int[] coinValue = new int[n];
        for(int i = 0; i < n; i ++) {
            coinValue[i] = Integer.parseInt(br.readLine());
        }
        

        for(int i = n - 1; i >= 0; i--) {
            while (k - coinValue[i] >= 0) {
                k -= coinValue[i];
                cnt++;

                if(k == 0)
                    break;

            }

        }
        bw.write(cnt + "\n");
        bw.flush();
        bw.close(); // 종료
    }
}

 

금액이 주어지고 가치가 정해진 동전의 종류가 주어진다. 

완전탐색느낌으로 풀었다. 근데 다른 사람 풀이를 보니 역시 나누기와 나머지 연산은 정말 좋은 연산자인 것 같다. 

 

cnt += k / coinValue[i]
k = k % coinValue[i]

이렇게 하면 더 빠르게 가능할 텐데 

이런 생각을 하는게 중요한 것 같다. 시간복잡도도 선형 시간 안에 끝난다.