[백준] 2839번: 설탕 배달 | C++ 풀이

# 문제

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

 

---

 

# 풀이

[한때는 이 문제가 "기본 수학 1" 단계에 있었지만, 사실 브루트 포스로 푸는 게 더 쉽습니다.]라고 한다.

브루트 포스로 풀어보자. 그럼 바로 정답 소스코드부터 확인!

 

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int cnt = 0;
    bool done = 0;
    while(n >= 0){
        if(n%5 == 0){
            cnt += n/5;
            done = 1;
            break;
        }
        n -= 3;
        cnt++;
    }
    if(!done) cout << -1;
    else cout << cnt;
    return 0;
}

이 문제는 최대한 적은 봉지를 사용해야 한다는 것이 키포인트다. 코드는 간단해보이지만 몇 번 실패했던 문제... 인데 지금 보니 왜지? 싶긴 하다.

우선 봉지 개수를 세어줄 cnt 변수, 정확하게 Nkg을 만들었는지 판단해줄 bool 타입 done 변수를 만들어준다.

그리고 while문 내에서 n이 0 이상일 경우, 아래의 계산과정을 반복해준다.

 

봉지를 최대한 적게 사용해야하므로 더 큰 단위인 5kg을 먼저 사용해준다. 만약 입력된 n이 5kg으로 나누어질 경우, cnt에는 n/5를 더해준다. 그리고 정확하게 떨어지므로 done 변수를 true로 변경 후 break! 아니라면 n에서 3kg을 한 번 빼주면서 cnt를 증가시키면 된다. 예시를 통해 다시 한번 확인해보자.

 

 

· 예를 들어 문제에서 입력된 18kg의 경우, 5로 나머지 연산을 해준 값이 0이 아니므로 3kg 봉지를 먼저 하나 사용해준다. (18-3 = 15, cnt++) 그 후 남은 15kg을 5로 나머지 연산을 하면 0이 되므로 15/5 = 3을 cnt 값에 더해 최종적으로 3kg 하나, 5kg 세 개, 총 네 개의 봉지를 사용한 것이 된다.

 

· 다음 입력인 4의 경우, 5로 나머지 연산을 해준 값이 0이 아니므로 3kg 봉지를 먼저 하나 사용해준다. (4-3 = 1, cnt++) 그 후 남은 1kg을 5로 나머지 연산을 했을 때 0이 아니므로 n -= 3의 과정을 거치는데 이때 몇개의 연산 과정을 거쳐 while문을 탈출하게 된다. 이 경우 while문 밖에서 확인했을 때 여전히 done 변수가 false이므로 -1을 출력해준다.

 

· 6의 경우, 5로 나머지 연산을 해준 값이 0이 아니므로 3kg 봉지를 먼저 하나 사용해준다. (6-3 = 3, cnt++) 그 후 남은 3kg을 5로 나머지 연산 했을 때 0이 아니므로 또 한 번 3kg 봉지를 사용한다. (3-3 = 0, cnt++) 마지막으로 while문으로 들어가 done을 true로 변경해주고 반복문 탈출! 3kg 봉지 두 개를 사용했으므로 2를 출력하면 된다.

 

 

 

 

 

---

 

 

2839번: 설탕 배달