Written by JS970
on
on
2839 - 설탕 배달
- 난이도: 실버 4
- 날짜: 2023년 2월 4일
- 상태: Correct
- 추가 검토 여부: No
solution
- 5와 3의 최소공배수인 15를 사용하여 문제를 풀이했다.
- 어떤 수가 3으로 나누어 떨어지지 않을 때 그 수에서 5를 빼거나 10을 뺀 수도 3으로 나누어 떨어지지 않는다면 해당 수는 $3x + 5y$의 형태로 나타낼 수 없는 수이다.(x, y는 정수)
- 봉지를 최소한으로 사용하는 경우는 5kg짜리 봉지를 최대한으로 사용한 경우이다. 이 경우를 찾기 위해 어떤 수가 3으로 나누어 떨어지고 몫이 5이상이 경우에 대해 조정을 해 주었다.
code
#include <iostream>
using namespace std;
int calc(int N)
{
int x = 0;
int y = 0;
if(N % 3 == 0)
{
x = N / 3;
while(x >= 5)
{
x -= 5;
y += 3;
}
return x + y;
}
else if(N % 5 == 0) return N / 5;
else return -1;
}
int main()
{
int N;
cin >> N;
int result = calc(N);
if(result != -1) cout << result << endl;
else if(N-5 > 0)
{
result = calc(N-5);
if(result != -1) cout << result + 1 << endl;
else if(N-10 > 0)
{
result = calc(N-10);
if(result != -1) cout << result + 2 << endl;
else cout << -1 << endl;
}
else cout << -1 << endl;
}
else cout << -1 << endl;
return 0;
}