항해99 30일차 TIL(설탕배달 / 백준)

문제         

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

1 번째 시도   

• 5킬로그램 봉지가 0개에서부터 5킬로그램 봉지의 최대 개수까지 탐색하며 답을 업데이트 한다.
• 만약 답이 한 번도 업데이트 되지 않는다면 정답이 없는 것이기 때문에 -1을 출력한다.

// 3, 5킬로그램 봉지가 있다.
// 최대한 5킬로그램 봉지를 많이 들고가야 한다.
// 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
    
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int max5 = N/5;
        int cnt5 = -1;
        int cnt3 = -1;
        for(int i =0; i <= max5; i++) {
            if((N - 5*i)%3 == 0) {
                cnt5 = i;
                cnt3 = (N - 5*i)/3;
            }
        }
        
        if(cnt5 != -1 && cnt3 != -1)  System.out.println((cnt5 + cnt3));
        else System.out.println(cnt5);
    }
}

결과

피드백

• 최댓값을 구하는 것이므로 5킬로그램 오름차순이 아닌 내림차순으로 탐색하면 더 빠를 것 같다.