[백준] 2839번: 설탕 배달 - java, C++

문제

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

 

접근법

우리가 거스름돈을 줄 때 최소 개수로 주기 위해서는 큰 단위 순으로 계산을 하면 된다. 예를 들어 12,530원을 거슬러줘야 하는 상황일 때 큰 단위 순으로 10,000원 2개, 1,000원 2개, 100원 5개, 10원 3개 이런 식으로 계산한다는 뜻이다.

이 문제도 비슷한 맥락으로 생각해보면 5kg으로 최대한 가져간 후, 남은 무게를 3kg으로 가져가면 된다. 이때 주의할 점은 5kg로 최대한 가져간 후 남은 무게가 3의 배수가 아닐 경우 3kg으로 남은 무게를 전부 배달할 수 없다는 것이다. 따라서 남은 무게가 최소한의 3의 배수가 될 때까지 5kg으로 배달하고 나머지는 3kg으로 배달해야 한다.

 

풀이

java

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());

        int c = N / 5; // 5kg 개수
        int remain = N - c * 5; // 남은 무게
        while(remain % 3 != 0) { // 남은 무게가 3kg의 배수가 아닌 경우
            remain += 5;
            if(remain > N) {
                c = -1;
                break;
            }
            c--;
        }
        if(c == -1) {
            System.out.println(-1);
        } else {
            c = c + remain / 3;
            System.out.println(c);
        }
    }
}

C++

#include <iostream>

using namespace std;

int N;

int main() {
    cin >> N;

    int answer = N / 5;
    N %= 5;

    while (N > 0) {
        if (N % 3 == 0) {
            answer += N / 3;
            break;
        }

        N += 5;
        answer--;
        
        if (answer < 0) {
            answer = -1;
            break;
        }
    }

    cout << answer;

    return 0;
}