[Baekjoon - 26099] 설탕 배달 2

난이도: Silver IV

 

태그

• Mathematics
• Greedy

 

풀이

1. 3 kg는 몇 개를 쓸 수 있을까?

3 kg를 5개 이상 썼다고 해봅시다.

그럼, 동일한 무게를 5 kg 3개로 만들 수 있겠죠.

 

이는, 3 kg를 최대 4개까지밖에 쓸 수 없음을 의미합니다.

 

2. 그럼, 문제의 답은?

3 kg의 봉지를 0개부터 4개까지로 돌리면서,

이에 맞는 5 kg의 개수가 존재하는지 보면 됩니다.

 

봉지의 개수를 최소화하려면 3 kg의 개수를 최소화해야 하니, 0부터 돌리면서 답이 나오는 순간 종료하면 되겠죠.

// 사실 0개부터 4개까지 중에서, 답이 될 수 있는 건 하나밖에 없습니다.

// 3x mod 5가 x = 0, 1, 2, 3, 4에 대해 모두 다르기 때문입니다.

 

3. 코드

void Main(){
    ll n; cin >> n;
    for (int c3 = 0; c3 < 5; c3++){
        ll x = n - c3*3; if (x < 0){ break; }
        if (x%5 == 0){ cout << c3 + x/5; return; }
    }
    cout << -1;
}