[백준] 2839번 : 설탕 배달 - Java(자바)

이번 문제는 설탕을 3, 5kg으로 배분하는 문제였습니다. 조건으로는 최대한 적은 봉지로 나눠지도록 지향한다는 점입니다. 예를 들어 18kg이라면 3kg씩 6봉지로 나누기보다 5kg 2봉지에 3kg 1봉지인 총 3봉지를 지향한다는 점입니다. 또한 4kg처럼 3kg와 5kg로 딱 맞게 나눌 수 없을 경우는 -1을 출력합니다.

Step 0. 해답 코드

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

public class Sugar_2839 {
	static int five = 0; // 5키로 봉지
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 설탕 kg 입력
		five = N / 5;
		System.out.println(search_suger(N, five));
	}
	public static int search_suger(int N, int five) { //재귀함수
		int three = 0; // 3키로 봉지
		three = (N - (five * 5)) / 3;
        	if (five == -1) {
			return -1;
		}
		if ((N - (five * 5)) % 3 ==  0) {
			return five + three;
		}
		return search_suger(N, five - 1);
	}
}

그렇게 어려운 문제는 아니었지만 익숙치 않은 재귀함수를 사용하여 생각을 좀 했던 문제였습니다.

Step 1. 문제 접근

어제 글에서 재귀함수를 쓰는 방법을 봤었다고 글에 썼었는데 오늘 문제를 보니 재귀로 풀 수 있겠다 싶어서 재귀함수를 활용하여 풀어봤습니다. 문제 풀이 방향은 입력된 총 kg인 N값을 우선 5로 나누어 몫을 구하고 나머지를 활용하여 3으로 곱해지는지 확인하였습니다. 3으로 나눠서 나머지가 없다면 5로 나눈 값 + 3으로 나눈 값을 더하고 나머지가 존재한다면, 즉 3으로 나눌 수 없다면 N을 5로 나눈 값을 1 줄여서 다시 3으로 나눠지는지 확인하는 식으로 재귀함수를 짰습니다.

Step 2. 문제 해결

우선 총 kg인 N을 받고 N을 5로 나눈 five와 five의 나머지를 3으로 나눈 three변수를 사용하였습니다. 저희가 원하는 것은 설탕 봉지를 최대한 적게 사용하는 것이기 때문에 그렇게 하기 위해서 최대한 5kg 봉지를 많이 사용하고자 하였습니다. 대략적인 알고리즘은 이와 같습니다.

1. N을 입력받고 five를 구해준다. (예로 N = 16이라면 five = 3)**

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 설탕 kg 입력
		five = N / 5;

2. five를 이용해 three를 구해준다. (식은 (N - (five * 5)) / 3 이지만 결국은 five 계산중 나오는 나머지 값 나누기 3을 한 것입니다. 저렇게 한 이유는 five값일 1씩 죽여주기 위해서입니다.)**

public static int search_suger(int N, int five) { //재귀함수
		int three = 0; // 3키로 봉지
        three = (N - (five * 5)) / 3;

3. 3으로 딱 나눠지면(나머지가 없다면) 잘 나눈 것이기에 출력해준다. (예를 들어 현재 five는 3이고 나머지는 1이기에 three의 나머지는 1이 됩니다. 즉 잘 나누어지지 않은 경우입니다. 잘 나누어진 경우라면 예를 들어 n = 18이라면 three의 나머지는 0, 몫은 1이기에 이러한 경우를 잘 나누어진 경우라고 할 수 있습니다.)****

if ((N - (five * 5)) % 3 ==  0) {
			return five + three;
		}

4. 나누어지지 않았다면 five의 값을 1 낮춰서 다시 3으로 나눠본다. (예를 들어 현재 N=16, five = 3(나머지 1), three = 0(나머지는 1)이므로 five를 2로 해서 five의 나머지를 6으로 높여 3으로 나눠지는지를 확인합니다.) 이러는 이유는 5로 나누는 값을 많이 쓸 수록 설탕 봉지의 수는 적어지기 때문입니다.

if (five == -1) {
			return -1;
		}
		if ((N - (five * 5)) % 3 ==  0) {
			return five + three;
		}
		return search_suger(N, five - 1);

5. 3으로 나눠질 때까지 4번의 방법을 반복한다. 단, five가 -1, 즉 범위를 벗어나면 해당 식은 딱 나눠지지 않는 경우기에 -1을 출력한다.

System.out.println(search_suger(N, five));

Step 3. 느낀 점

이번 문제는 그렇게 어렵지는 않았지만 익숙하지 않은 재귀함수를 사용해서 조금 더 시간이 걸렸던거 같습니다. 하지만 이 시간이 아깝거나 그렇진 않고 오히려 여러 문제 풀이 방식을 사용할 수 있어서 좋은 시간이었다고 생각합니다.

출처 : 백준 2839번 https://www.acmicpc.net/problem/2839