취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26099번 문제인 설탕 배달 2이다.
문제는 아래 링크를 확인하자.

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

설탕 15kg를 배달할 때 3kg 봉지 5개를 배달하는 것보다 5kg 봉지 3개를 배달하는 것이 항상 봉지 수가 더 적음을 관찰하자.

따라서 0 이상 15 미만의 N에 대한 답(불가능이 있을 수 있음)과 15 이상 30 미만의 N에 대한 답(불가능한 경우가 없음)을 구해둔다면 위의 관찰을 이용해 모든 경우의 답을 간단한 연산만으로 구할 수 있게 된다.

한편, 30 미만의 답의 경우 주어진 수를 5로 나눈 나머지가 0이 될 때까지 3kg 봉지를 가져가고 남은 무게를 5kg 봉지로 가져가는 전략으로 구해지는 값과 같음을 관찰할 수 있다.

그러므로 이 문제의 답은 5로 나눈 나머지가 0이 될 때까지 3kg 봉지를 가져가고(단, 그 과정에서 더 가져가야하는 무게가 음수가 된다면 -1 출력) 남은 모든 무게를 5kg 봉지로 가져가는 것으로 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N, ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N % 5) N -= 3, ans++;

	if (N < 0) cout << -1;
	else cout << ans + N / 5;
}