2839번 설탕 배달

 그리디 알고리즘

 

 1. N을 각각 5과 3로 나누고 나머지가 없으면 그 몫을 저장한다. (배열 arr3, arr5)

 2.  (arr3*3 + arr5*5) = N 인 값을 찾으면 된다. (찾아서 제일 작은 값을 구한다)

 

	0	1	2	3	4	5	6
3	0	0	0	1	0	0	2
5	0	0	0	0	0	1	0

 

 

import java.util.Scanner;
 
public class Problem2839 {
 
    public static void main(String[] args) {
        
        final int MIN = 987654321;
        
        int ans = MIN;
        int num = 0;
        
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt();
        
        int[] arr3 = new int[N+1];
        int[] arr5 = new int[N+1];
        
        for(int i=1;i<=N;i++) {
            if(i%3==0) {
                arr3[i] = i/3;
            }
            
            if(i%5==0) {
                arr5[i] = i/5;
            }
        }
        
        for(int i=0;i<=N;i++) {
            for(int j=0;j<=N;j++) {
                if((arr3[i]*3+arr5[j]*5)==N) {
                    num = arr3[i]+arr5[j];
    
                    ans = Math.min(ans, num);
                }
            }
        }
        
        if(ans==MIN) {
            System.out.println(-1); 
        } else { 
            System.out.println(ans); 
        }
         
    }
}