백준 11047 자바 및 C++

풀기 전:

다행히 정렬이 되어 있기때문에 처음으로 k값보다 arr[i]값이 작을때, k의 상당 부분을 제거할 수 있을 것이다.

자바(JAVA)

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Collections;
public class Main{
    public static void main(String[] args) throws IOException {
       Scanner scanner=new Scanner(System.in);
       int n=scanner.nextInt();
       int k=scanner.nextInt();
       int arr[]=new int[n];
      for(int i=0;i<n;i++){
          arr[i]= scanner.nextInt();
      }
      int count=0;
      for(int i=n-1;i>=0;i--){
          if(k==0){
              break;
          }
          if(arr[i]<=k){
              count+=k/arr[i];
              k%=arr[i];
          }
      }
      System.out.println(count);

    }
}

C++

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int main(void) { 
	int n;
	cin >> n;
	int k;
	cin >> k;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int count = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (k == 0) {
			break;
		}
		if (arr[i] <= k) {
			count += k / arr[i];
			k %= arr[i];
		}
	}
	cout << count;

}

6개월 후에 다시 풀었을 때:
이미 정렬이 되어있고 arr[i]가 arr[i-1]의 배수라는 조건이 있어서 그리디 알고리즘으로 풀 수 있음을 보증한다. 만약 이게 없으면 그리디만으로는 풀 수 없을 것이다.

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       Scanner scanner=new Scanner(System.in);
       int n=scanner.nextInt();
       int k=scanner.nextInt();
       int arr[]=new int[n+1];
       for(int i=1;i<=n;i++){
           arr[i]=scanner.nextInt();
       }
       int current=n;
       int count=0;
       while(k!=0||current!=0){
           if(k/arr[current]!=0){
               count+=k/arr[current];
               k=k%arr[current];
           }
           current--;
       }
        System.out.println(count);

    }


}