[백준] 2839번 : 설탕 배달 (C++)

코딩 테스트

[백준] 2839번 : 설탕 배달 (C++) - 실버 4

taks-embdd 2025. 1. 31. 02:24

이 문제는 백준 알고리즘에서 제공하는 단계별 문제 풀이 중 '브루트 포스' 단계에 해당한다.

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

해당 문제는 주어진 임의의 N이라는 정수에 대하여 가장 적은 x개의 3과 y개의 5의 합으로 표현하는 전형적인 브루트 포스 문제이다.

왜냐하면 주어진 조건 중, 두 수의 합으로 나타낼 수 없는 수에 대하여 -1을 출력해야 하는데, 나타낼 수 있는지에 대한 여부는 결론에 도달할 때까지 계산을 해봐야 하기 때문이다.

문제 해결 시 고려 사항이다.

N : 설탕 봉지 수
설탕 봉지 무게 : 3 || 5
가장 적은 봉지 수로 표현되어야 함
3과 5의 합으로 표현하지 못할 경우 -1 출력

위의 조건에 맞게 먼저 변수 초기화 후, 입력값을 받는다.

int N, cnt = 0;

cin >> N;

이미 알고 있을수도 있지만, 변수 중 N은 초기화 값을 설정하지 않고, cnt는 굳이 0으로 초기화한 건 기존 메모리의 쓰레기 값을 지워야하는 변수에 대한 차별점이다.

N의 경우, 입력값이 대입되기 때문에 특정 값으로 초기화할 필요가 없지만, 뒤의 코드를 보면 cnt의 경우 값을 누적하기만 할 뿐, 새롭게 대입하고 시작하는 코드가 없다.

cnt += (N / 5)의 경우에도 결국 cnt = cnt + (N / 5)이므로 기존의 cnt 값에 N을 5로 나눈 결과에 대해서 더하는 코드이다.

이때, 이상한 값이 결과로 출력될 수 있는데, 이는 컴파일된 파일이 실행되면 메모리에 프로세스가 적재되는데, 이 과정에서 새로이 메모리 공간을 할당받을 때 기존에 사용되던 값이 지워지지 않고 남아있는 경우 85692347처럼 터무니 없는 숫자가 남아있을 수도 있다. 이를 쓰레기 값(Garbage value)이라고 하며, 위의 cnt = 과 같은 코드를 통해 새로운 값으로 메모리 공간을 덮어 씌워 쓰레기 값을 지우는 초기화 과정을 거친다.

다음으로 설탕 봉지 수 계산을 위한 반복문이다.

while (N >= 0) {
    if (N % 5 == 0) {
        cnt += (N / 5);
        cout << cnt << "\n";
        break;
    }
    
    N -= 3;

    if (N < 0) {
        cout << "-1" << "\n";
        break;
    }
    else {
        cnt++;
    }
}

이 코드의 핵심은 바로 '3과 5라는 숫자를 어떤 순서로 처리했는가'이다.

만약 5를 먼저 나누고, 나머지를 가지고 3에 대한 연산을 진행하려하면, 5로 먼저 나누지 않았어야만 올바른 답이 나오는 숫자들이 있다.

11을 예로 들어보자. 5로 먼저 나누게 되면 나머지가 1이기 때문에 -1을 출력해야한다. 그러나, 이 숫자는 3 * 2 + 5 * 1로 표현 가능하다.

그렇다면, 3으로 먼저 나눈다면 어떻게 될까?

18을 예로 들어보자. 18을 3으로 나누면 6으로 나누어떨어져 얼핏 생각하면 정답일 수 있지만, 18 = 3 * 1 + 5 * 3으로 표현 가능하므로 이 또한 잘못된 접근이다.

이 문제의 본질은 '가장 적은 수의 3과 5의 합을 통해 주어진 수를 도출하는 것'이다.

이를 다르게 표현하면, 5가 많으면 많을수록 봉지 수의 총합이 적어진다는 것이다.

하지만, 먼저 나누는 과정을 실행했을 때는 주어진 수에 대하여 나눗셈이 곧바로 실행되기에 올바른 답을 도출할 수 없었다.

작성자는 이러한 특성을 기준으로 잡고 고민한 결과, '3의 개수가 최대한 적은 것 또한 5의 개수가 많아지는 것과 같은 의미 아닌가?'라는 아이디어가 떠올랐고, 5로 나누어 떨어지는지 확인하고, 만약 그렇지 않다면 N에서 3을 빼고 3의 개수를 하나 더하는 과정을 저장하는 변수에 갱신하여 3에 대한 연산 횟수는 최소화하면서 5의 개수는 최대화하는 방식을 만들었다.

이렇게 되면 브루트 포스의 본질을 이용하여 3과 5에 대한 조건 확인 및 연산을 입력값이었던 N이 0이 될때까지 진행할 수 있게 된다.

위의 내용을 병합한 코드 전문은 다음과 같다.

#include <iostream>

using namespace std;

void fast_io() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    fast_io();
    int N, cnt = 0;

    cin >> N;

    while (N >= 0) {
        if (N % 5 == 0) {
            cnt += (N / 5);
            cout << cnt << "\n";
            break;
        }
        N -= 3;

        if (N < 0) {
            cout << "-1" << "\n";
            break;
        }
        else {
            cnt++;
        }
    }
}