[2839] 설탕 배달

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

2839번: 설탕 배달

 

---

 

되게 간단한 문제였는데 계속 88%에서 틀렸다고 떠서 너무 짜증났던 문제...

4kg와 같이 정확하게 nkg을 만들 수 없는 경우 -1을 출력하지 않고 있었기 때문에 그랬던 것이다.

 

---

 

🔎 해결 방법 

가능하다면 3kg보다는 5kg 봉지를 많이 사용하는 것이 총 봉지의 개수를 줄일 수 있는 방법이기 때문에

1. n이 5로 나누어 떨어진다면, 5kg 봉지만 사용하여 배달

2. 그렇지 않다면 n에서 3, 6, 9... 을 차례로 뺀 값을 5로 나눈 뒤,

그 나머지가 3이라면 5kg와 3kg만 가지고 배달할 수 있다는 소리이기 때문에

n에서 3, 6, ...을 뺀 값을 5로 나눈 몫이 5kg 봉지의 개수, i + 1 이 3kg 봉지의 개수가 된다. 

 

말로 풀어쓰면 잘 이해가 안되니 예시를 통해서 간단하게 설명해보겠다.

 

예를 들어 16kg을 배달하고자 한다면,

 

-> 나머지가 1이므로 그 다음 단계(for문) 진행

 

 

-> 나머지가 3이므로 16kg 는 5kg x 2, 3kg x 2 개로 배달할 수 있다!

 

---

 

💡 내 코드(C++) 

// [2839] 설탕 배달
// https://www.acmicpc.net/problem/2839

#include <iostream>
using namespace std;

int main(void)
{
    int n, three = 0, five = 0; // 상근이가 배달해야하는 무게, 3kg 봉지 개수, 5kg 봉지 개수
    cin >> n;

    if (n % 5 == 0) {
        five = n / 5;
        cout << three + five;
        return 0;
    }
    
    for (int i = 0; (n - i * 3) > 0; i++) {
        if ((n - i * 3) % 5 == 3) {
            five = (n - i * 3) / 5;
            three = i + 1;
            cout << three + five;
            return 0;
        }
    }
    
    cout << "-1" << endl;
}