[BOJ] 2839. 설탕 배달 (Java)

www.acmicpc.net/problem/2839 (level: Bronze I)

2839번: 설탕 배달

---

많은 고민을 한 흔적들😂

작년에 단순하게 접근했다가 런타임 에러 난 이후로 그냥 방치해뒀었는데, 새로운 마음으로 다시 풀어보았다.

 

분류는 그리디로 되어있는데 나는 수학적으로 접근해서(나머지를 이용해 규칙을 찾아냄,,😂) 결국 성공하긴 했다. 그리디로 푸는 방법은 잘 생각이 안 난다. 아니, 그전에 일단 3과 5라는 숫자를 이용하려면 서로 배수관계가 아니기 때문에 이전에 풀었던 동전이나 거스름돈 문제들처럼 가장 큰 수부터 순서대로 쭉 처리해주는 방식으로는 풀 수가 없다. 

 

핵심은

1. 나머지를 구한다.

2. 그리고 3kg와 5kg 중 단위가 더 큰 것은 5kg이므로 가능한 나머지 = 0,1,2,3,4마다 어떻게 처리해줄지 고민.

 

<나머지마다 어떻게 처리해줄건데?>가 내 로직의 진짜 핵심이라고 볼 수 있겠다.

1. 우선, 나머지가 0일 때와 3일 때가 처리가 쉬워서 먼저 해결해봤다. (※주관적인 기준임^_^)

나머지가 0인 경우, 즉, N이 5의 배수인 경우 5kg짜리로만 다 채우는 것이 최소 개수이므로 몫을 구해 처리.

나머지가 3인 경우에는 5kg를 최대한으로 넣고(그래서 처음에 N을 5로 나눈 몫을 구하는 것), 남은 수는 3의 배수이므로 3kg짜리로 다 채워준다. 이때 최소 조건을 충족한다.

 

2. 나머지가 1,2,4인 경우 각각의 규칙을 찾아냈다.

나머지가 1인 경우, 3kg를 2개 사용하면 5의 배수가 된다.

나머지가 2인 경우, 3kg를 4개 사용하면 5의 배수가 된다.

나머지가 4인 경우, 3kg를 3개 사용하면 5의 배수가 된다.

 

따라서 각각의 경우 N=6kg / N=12kg / N=9kg 미만이면 어떻게 해도 문제에서 주어진 3kg와 5kg를 가지고 원하는 무게를 만들 수가 없으므로 불가능 처리해준다. (cnt = -1)

한편, 해당 무게 이상을 만족한다면 cnt를 필요한 사용개수만큼 증가시켜주고 업데이트 된 N는 5의 배수이므로 1에서 5의 배수를 처리해줬던 방식과 똑같이 처리해주면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/* @date: 2021/05/05
 * @author: psS2mj
 * @brief: BOJ_2839_설탕 배달 */

public class BOJ_2839_설탕배달 {

	static int N, div, cnt = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		div = N % 5;
		
		switch (div) {
		case 0:
			cnt += N / 5;
			break;
		case 1:
			if (N < 6) {
				cnt = -1;
			} else {
				cnt += 2;
				N -= 6;
				cnt += N / 5;
			}
			break;
		case 2:
			if (N < 12) {
				cnt = -1;
			} else {
				cnt += 4;
				N -= 12;
				cnt += N / 5;
			}
			break;
		case 3:
			cnt += N / 5;
			N -= 5 * cnt;
			cnt += N / 3;
			break;
		case 4:
			if (N < 9) {
				cnt = -1;
			} else {
				cnt += 3;
				N -= 9;
				cnt += N / 5;
			}
			break;
		}

		System.out.println(cnt);

	} // main

}

 

나는 switch문 성애자이므로 이 문제에서도 나머지에 따라 각각의 로직을 수행시키라고 switch문을 써봤다.

 

div(나머지)가 1,2,4일 때 한꺼번에 밑에서 처리해주려고 break; 안 걸고 아래에 cnt += N / 5;를 써놨다가 case 1을 거쳐 case 2를 거쳐 case 4를 거치는 바람에 엉망진창 돼서 삽질 좀 했지만.. 덕분에 얻어맞으면서 개념이 다시 돌아왔다. switch문에서 로직은 각각의 case 안에서 끝내도록 하자!!!😂

 

Scanner보다 BufferedReader를 생활화하자!

기록을 보면 1년 전에 런타임 에러로 털렸던 흔적이 남아있다.

저 뒤로 다시 풀어보질 않았었는데, 그리디 알고리즘 문제에 속해있길래 새로운 마음으로 도전해봤으나 정작 그리디로 푼 것 같지는 않고… 그냥 수학적으로 접근해버렸는데 이따 다른 사람들 풀이도 한 번 봐야겠다!🤔🙄

 

*tmi: 처음에 틀렸다고 나온건 내가 switch문 쓰다가 break; 안 걸고 한꺼번에 처리한다고 깝치느라 다른 케이스들 로직까지 수행해버려서 엉망진창 됐었음. 그 뒤로는 바로 고쳐서 맞힘!🙆🏻‍♀️ => 반례 다 해보다가 그냥 1부터 다 넣어보고 있었는데 7에서 틀린게 감지되고 그 이후 깨달음.

 

그리고 이 문제는 특별히 입력 받을 게 없어서 처음에는 그냥 간단하게 스캐너를 사용했다가 108ms가 찍혔는데, 고치는 김에 BufferedReader로 해봤는데 속도 차이가 유의미하게 나긴 하는 듯. 80ms, 72ms 찍혔으니까. 그냥 정수 N 하나만 받을 때도 이 정도 차이인 걸 보면 그냥 항상 BufferedReader 쓰는 게 나을 것 같다.

 

그리고 뭔가 전체적으로 비슷한 로직이 여러 군데 있는 느낌이라 최적화 할 수 있을 것 같은데, 당장은 일단 맞힌 것만 해도 만족하고 머리를 더 쓰고 싶지 않아서 일단 오늘은 여기서 마친다. 나중에 힘이 날 때 최적화를 하든 다르게 접근해보든 해봐야겠다. 그럼 이만🏃🏻‍♀️=3=3