[백준(baekjoon)] (Greedy 알고리즘) 설탕배달

알고리즘 문제 풀이 / 백준 (baekjoon)  - 설탕배달

 

 

문제 링크

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

2839번: 설탕 배달

 

 

문제 풀이

 

5kg 으로 나누어지는 최대부터 구한다.

 

백준 문제를 처음 풀어보았다. 클래스부터 직접 작성해야했고, 입력예제도 직접 받아야 한다는 점에서 프로그래머스보다 불편했다. 하지만 많은 문제들이 있어 풀어보려고 오늘 처음 시도해보았다. 수 많은 문제들 중 무엇부터 풀어야하나 고민하다 알고리즘 별로 풀어나가려고 해서 Greedy 부터 시작했다. Greedy 카테고리중 첫 문제인 설탕배달을 풀어보았다. 최소한의 개수를 가지고 가려면 5kg이 제일 많을 때가 최소이므로 5kg 의 최대부터 구하면서 3kg로 나누어떨어질때가 최소인것으로 풀었다. JAVA 11로 풀었을 때 걸린 최소 시간은 120ms 으로 세명이 있었고 다음은 124ms 였는데 내 코드가 124ms 이다. 120ms 인분들은 나누는 모든 경우의 수들을 if문으로 나열해 풀었는데 숫자가 바뀌면 효율적이지 않단 생각에 내 코드를 바꾸어보진 않았다.

 

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str = br.readLine();
	int n = Integer.parseInt(str);
	br.close();
    
	int mok = n / 5; 
	int min = n;
	for(int i = mok; i >= 0; i--) {
		int na = n;
		na -= i * 5;
		if(na % 3 == 0) {
			min = na / 3 + i;
			break;
		}
	}
		
	int answer = min != n ? min : -1;
	System.out.println(answer);
}