11047 동전 0 (JAVA)

• 목표값보다 작은 동전들 중 가장 큰 동전부터 갯수를 세어나가면 되는 그리디 알고리즘 기초 문제.
• 냅색 알고리즘으로 해결하기 위해서는 최대 목표값인 100,000,000의 크기를 갖는 배열을 생성해야 하는데 이는 불가능하다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];	// 동전이 담길 배열
        
        int target = sc.nextInt();	// 목표 값
        
        for(int i=0; i<n; ++i)
            arr[i] = sc.nextInt();

		/* 목표 값보다 작은 동전들 중 가장 큰 값 탐색 */
        int start = n-1;
        for(int i=n-1; i>=0; i--){
            if(arr[i] <= target) {
                start = i;
                break;
            }
        }
        if(n==1)	// 동전이 하나 들어올 경우
            start = 0;

        int temp = 0;
        int count = 0;
        // 목표값과 같아지면 제1 for 문도 종료
        for(int i = start; i>=0 || temp!=target; --i){
            while(true){
                if(temp + arr[i] > target)
                    break;
                else {
                    temp += arr[i];
                    count++;
                }
                if(temp == target)
                    break;
            }
        }
        System.out.println(count);
    }
}