less than 1 minute read

πŸ“Œ λ‚œμ΄λ„

πŸ₯ˆ Silver 4


πŸ“Œ 문제

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


image

image


πŸ“Œ 풀이

Greedy μ•Œκ³ λ¦¬μ¦˜μ„ 배우고 처음으둜 ν’€μ–΄λ³΄λŠ” κ΄€λ ¨λœ 문제라 살짝 κΈ΄μž₯ν•œ μƒνƒœλ‘œ ν’€μ—ˆλ‹€.
ν•˜μ§€λ§Œ ν’€μ–΄λ³΄λ‹ˆ ν‰μ†Œμ— ν‘ΈλŠ” λ¬Έμ œμ™€ λΉ„μŠ·ν•΄μ„œ 쉬웠닀.

target을 λ°›κ³ , λ™μ „μ˜ κ°€μΉ˜λ₯Ό coinsλΌλŠ” 배열을 λ§Œλ“€μ–΄μ„œ 넣은 ν›„, coins에 λ“€μ–΄μžˆλŠ” κ°’μœΌλ‘œ μ°¨λ‘€λŒ€λ‘œ λ‚˜λˆ μ„œ λ‚˜λˆˆ λͺ«μ€ result에 μΆ”κ°€μ‹œν‚€κ³ , λ‚˜λ¨Έμ§€λŠ” λ‹€μ‹œ λ‹€μŒ μ£Όμ†Œμ— μžˆλŠ” κ°’μœΌλ‘œ λ‚˜λˆ„μ—ˆλ‹€.

λ§ˆμ§€λ§‰μœΌλ‘œ resultλ₯Ό 좜λ ₯ν•˜μ˜€λ‹€.


πŸ“Œ Code

package Greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N11047 {
    public static int[] coins;
    public static int count;

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

        count = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());
        coins = new int[count];

        for (int i = 0; i < count; i++) {
            st = new StringTokenizer(br.readLine());
            coins[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(MinCoins(target));
    }

    public static int MinCoins(int target) {
        int result = 0;
        for (int i = count - 1; i > -1; i--) {
            result += target / coins[i];
            target = target % coins[i];
        }
        return result;
    }
}

package (이름); λ₯Ό λ•Œκ³ , class 이름을 Main으둜 λ³€κ²½ν•˜λ©΄ λœλ‹€.



개인 곡뢀 기둝용 λΈ”λ‘œκ·Έμž…λ‹ˆλ‹€.
ν‹€λ¦¬κ±°λ‚˜ 였λ₯˜κ°€ μžˆμ„ 경우 μ œλ³΄ν•΄μ£Όμ‹œλ©΄ κ°μ‚¬ν•˜κ² μŠ΅λ‹ˆλ‹€.😁