[java] 문제 032 (백준 11047)

문제

동전 개수의 최솟값 구하기

 

교재 풀이

import java.util.Scanner;
public class P11047_동전개수최솟값 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    int count = 0;
    for (int i = N - 1; i >= 0; i--) {
      if (A[i] <= K) { // 현재 동전의 가치가 K보다 작거나 같으면 구성에 추가한다.
        count += (K / A[i]);
        K = K % A[i]; // K를 현재 동전을 사용하고 남은 금액으로 업데이트 함
      }
    }
    System.out.println(count);
  }
}

 

내 풀이) 24.6.18에 풀고 맞음

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

public class Main
{
	public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] a=new int[n];
        
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        
        long ans=0;
        for(int i=n-1;i>=0;i--){
            ans+=k/a[i];
            k%=a[i];
            
            if(k==0){
                break;
            }
        }
        
        System.out.println(ans);
    
	}
}

// 		1줄에 n,k가 입력됨
// 		    n은 동전 종류, k는 가격의 합
// 	    2줄에 n개의 동전 가격이 오름차순으로 입력됨
//         동전 최솟값
        
//         접근법
//             그리디고, 대표적인 문제임
//         슈도코드
//             n,k를 입력받음 
//             동전 종류 받는 배열 a: 크기 n
//             for n번 반복해서 
//                 a에 입력받기 
            
//             ans=0: 필요 동전 개수 
//             일단 k를 a[i]로 계속 나누고 그런 과정 필요
//                 for n번 반복 
//                     ans+= k / a[i]
//                     k=k%a[i]
//                         만약 k가 4500, a[i]가 10000이면
//                         4500이 되고, 
//                         만약 a[i]가 1000이면 
//                         몫은 4고, 나머지는 500이고 
//                         즉 몫 한 번 나누고, 나머지도 나누고 이를 반복 
                        
//                      k가 0이면 break

 

설명

그냥 그리디 대표 문제임