[코드트리/INTERMEDIATE MID] 동전 더하기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 그리디

. 큰 동전부터 사용한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int[] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        arr = new int[N];
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        int cnt = 0;
        for(int i = N - 1 ; i >= 0 ; i--) {
            if(K / arr[i] > 0) {
                int tmp = K / arr[i];
                cnt += tmp;
                K -= arr[i] * tmp;
            }
        }
 
        System.out.println(cnt);
    }
}

 

 

 

➕ 다른 풀이 방식

1) 

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int[] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        arr = new int[N];
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        int cnt = 0;
        for(int i = N - 1 ; i >= 0 ; i--) {
            cnt += K / arr[i];
            N %= arr[i];
        }
 
        System.out.println(cnt);
    }
}

 

 

2) while문을 활용하셨다.

import java.util.*;
import java.io.*;
 
public class Main {
    static int n, k;
    static int[] board;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));
 
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);
 
        board = new int[n];
        for(int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(br.readLine());
        }
 
        int cnt = 0;
        int idx = n - 1;
 
        while(k != 0) {
            if(k - board[idx] >= 0) {
                k -= board[idx];
                cnt++;
            }
            else {
                idx--;
            }
        }
 
        System.out.println(cnt);
    }
}

 

---

🧐 새로 알게 된 내용

- 동전 종류가 배수 관계로만 나타내질 때는, 큰 동전부터 사용하는 것이 항상 유리하다 !

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리