[백준/파이썬(Python), 자바(JAVA)] 동전0 11047 Silver 4

💌문제

---

 

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

11047번: 동전 0

 

💌풀이

---

그리디 알고리즘 문제이다.

그리디 알고리즘이란, 최적의 솔루션을 찾기 위해 알고리즘의 각 단계에서 최적의 선택을 하는 수학적 최적화 기법이다.

솔루션을 반복적으로 구성하여 최적화 문제를 해결하는데 사용하며, 항상 현재 사용 가능한 최상의 값을 선택한다.

이러한 그리디 알고리즘은 구조가 단순한데, 개인적으로는 솔루션 떠올리는게 어려운 것 같다.

또한, 그리디는 간단하고 효율적이지만 항상 최적의 솔루션이 나오지는 않을 수 있다. 이럴 때는 DP등의 다른 알고리즘을 사용해야 한다.

 

아래 코드에 대한 설명은 다음과 같다.

for 루프를 뒤에서부터 돌면서 k//현재 동전 가치 해서, 그 값이 0보다 크면 answer에 k//현재 동전 가치를 더한다.

그리고 k에는 k%현재 동전 가치를 저장한다.

 

💌파이썬 코드

---

n,k=map(int,input().split())
coin=[]

for _ in range(n):
    coin.append(int(input()))

answer=0
coin.sort()
for i in range(n-1,-1,-1):
    # print(k%coin[i])
    if k//coin[i]>0 :
        answer+=k//coin[i]
        k%=coin[i]


print(answer)

💌자바 코드

---

package org.example;

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

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<n;i++){
            coin[i]=Integer.parseInt(br.readLine());
        }
        int answer=0;
        for(int i=n-1;i>-1;i--){
            if(k/coin[i]>0){
                answer+=k/coin[i];
                k%=coin[i];
            }
        }
        System.out.println(answer);
    }
}