[Baekjoon] 2839 - 설탕 배달

📝 문제

 

 

🔑 풀이 과정

이 문제 풀이의 핵심 포인트는 2가지이다.

① 정확하게 N킬로그램을 만드는 것

② 최대한 적은 봉지를 쓰는 것(→ 5킬로그램 봉지를 최대한 많이 써야한다)

 

일단 N을 5로 나눈 몫 = 최대한 쓸 수 있는 5킬로그램 봉지의 개수

N에서 (5*몫)을 뺀 값을 3으로 나눈 나머지를 구한다.

 

(1) 3으로 나누어 떨어진다면(나머지가 0이라면), 봉지를 최소한으로 사용하고, 5와 3으로 N을 완성할 수 있다는 뜻.

→ 5킬로그램 봉지 개수, 3킬로그램 봉지의 개수를 더한 후 반복문 탈출

(2) 만약 나누어 떨어지지 않는다면, 5와 3으로 N을 만들수 없다는 것 (현재의 5킬로 봉지 개수로)

→ 5킬로그램 봉지의 개수를 하나 감소시킨후, 다시 앞의 과정을 반복

 

만약 감소를 반복하다 5킬로그램 봉지의 개수가 음수가 되면, 3과 5로 정확히 N을 만드는 경우가 없다는 뜻이므로 반복문 종료.

 

[예제 3으로 예시들기]
N = 6

6 / 5 = 1
현재 5킬로봉지의 개수 = 1개
6 - (5 * 1) = 1
1은 3으로 나누어 떨어지지 않음
→ 5킬로봉지의 개수 감소시킴

현재 5킬로봉지의 개수 = 0개
6 - (5 * 0) = 6
6은 3으로 나누어 떨어짐
→ 5킬로봉지의 개수: 0개
→ 3킬로봉지의 개수: 6 / 3 = 2개

 

 

🔓 답안

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        int ans = -1;
        int A = N / 5; //5킬로그램 봉지 개수
        int B; //3킬로그램 봉지 개수
        while(0 <= A){
            if((N-(5*A)) % 3 == 0){
                B = (N-(5*A)) / 3;
                ans = A + B;
                break;
            } else{
                A--;
            }
        }

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 다이나믹 프로그래밍

- 그리디 알고리즘