[그리디] 백준 26099번 설탕 배달2 - JAVA

 

정!말! 오랜만에 코딩테스트 공부하러 왔다 ㅠㅠ

6월, 방학과 따로 추가적인 팀프로젝트 진행하면서

면접 보느랴 프젝 공부하느랴 바빴는데...

그래도 알고리즘은 감 떨어지면 안되기 때문에...!!

 

내가 저번 학기에 못풀었던 문제들을 다시 풀어보고자 한다!

 

 

 

---

1. 출처

---

 

26099번: 설탕 배달 2

 

 

2달전... 시간 초과 났던 그 문제...

다시 풀어보기 스타트!

 

 

 

---

2. 설계 및 전체 코드

---

여기서 주목 한 것은 3kg, 5kg의 설탕봉지이다. 우리가 덜 배달을 가려거든 5kg 봉지를 최대한 많이 가져가야 한다.

그래서 5kg로 딱 나눠 떨어지면, 모든 설탕 kg을 모두 5kg로 가져가는 방향이다. 3kg씩 빼가다가 5kg로 나눠 떨어지면, 모두 5kg로 교환하는 방법을 사용했다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long kg = sc.nextLong();
		long count = 0;
		
		//5로 나눠지지 않을 때까지 3을 빼준다.
		while(kg%5!=0 && kg>0) {
			kg-=3;
			count++;
		}
		
		//5로 나눠진다고 판단되면 count + 5로 나눈 
		//5로 나눠진다고 판단안되면 -1
		if(kg%5==0) count += kg/5;
		else count = -1;
		
		System.out.println(count);

	}

}

3kg를 계속 가져가다가 음수가 남거나 5kg로 나눠 떨어지지 않는 설탕 kg을 가졌을 경우에는 -1을 출력한다.

 

여기서 주의해야 하는 점은 10^18까지 입력 받을 수 있어서 long 타입, nextLong()을 썼어야 했다는 점이다.

 

 

---

시간 제한이 0.25이기에 DP로는 풀릴 수 없던 문제