[백준알고리즘] 2839 - 설탕 배달

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

2839번: 설탕 배달

 

이 문제는 의도와는 다르게 다소 복잡하게 해결한 것 같습니다...ㅠㅠ 추후에 다른 풀이를 보고 다시 풀어보겠습니다... 우선 지금 해결한 풀이를 설명하겠습니다.

 

1. 설탕 봉지를 최소로 하면서 정확한 양의 설탕을 배달해야하기 때문에 우선 5kg 설탕을 최대한 많이 가져갑니다.

2. 그 이후에 3kg 설탕을 하나씩 증가시키며 설탕 무게를 맞춥니다.

3. 만약 설탕의 무게가 가져가려는 무게와 맞다면 이때 5kg 설탕 봉지 수와 3kg 설탕 봉지 수를 더해 값을 리턴합니다.

4. 설탕의 무게가 가져가려는 무게보다 커지는 경우에는 다시 5kg 설탕 봉지 수를 하나씩 감소시키면서 2, 3번 과정을 반복합니다.

5. 5kg 설탕 무게가 0이면서 이때까지 설탕의 무게를 맞출 수 없는 경우 -1을 리턴합니다.

 

자바 코드는 다음과 같습니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(calculateSugarCount(n, n / 5));

    }

    private static int calculateSugarCount(int n, int fiveCount) {
        int answer = -1;

        int threeCount = 0;
        while (true) {
            // 설탕의 무게가 초과된 경우
            if (n < (fiveCount * 5) + (threeCount * 3)) {
                break;
            }
            
            // 설탕의 무게를 맞춘 경우
            if (n == (fiveCount * 5) + (threeCount * 3)) {
                answer = fiveCount + threeCount;
                break;
            }
            
            // 3kg 설탕을 증가시키면서 설탕 무게 맞추기
            threeCount++;
        }

        // 설탕 무게를 아직 구하지 못한 경우
        if (fiveCount != 0 && answer == -1) {
            // 5kg 설탕 봉지 수를 줄이고 다시 구하기
            answer = calculateSugarCount(n, fiveCount - 1);
        }

        return answer;
    }
}