[λ°±μ€] π₯ 11047 λμ 0
π λμ΄λ
π₯ Silver 4
π λ¬Έμ
https://www.acmicpc.net/problem/11047
π νμ΄
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
μΌλ‘ λ³κ²½νλ©΄ λλ€.
κ°μΈ κ³΅λΆ κΈ°λ‘μ© λΈλ‘κ·Έμ
λλ€.
ν리거λ μ€λ₯κ° μμ κ²½μ° μ 보ν΄μ£Όμλ©΄ κ°μ¬νκ² μ΅λλ€.π