2839 설탕 배달
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int sum = 0;
if(N%5==0) {
sum +=N/5;
System.out.println(sum);
return;
}
int a= N;
while(3<=a) {
a = a-3;
sum+=1;
if(a%5==0) {
sum+=a/5;
System.out.println(sum);
return;
}else {
continue;
}
}
sum = 0;
if(N%3==0) {
sum+=N/3;
System.out.println(sum);
return;
}
System.out.println(-1);
}
}
배달하려는 봉지 - 두가지 경우
<1> 봉지의 무게가 3의 배수와 5의 배수 합으로 이루어져 있다. => 5a+3b (a,b는 0 이상)
1) 봉지의 무게가 5의 배수이다. => 5a (이 경우, b=0)
- 예를 들어, 5, 10, 15..
2) 봉지의 무게가 3의 배수 + 5의 배수로 이루어져 있다. => 5a+3b (a,b는 반드시 1이상)
- 예를 들어, 8, 11, 13...
3) 봉지의 무게가 3의 배수이다. => 3b (이 경우, a=0)
- 예를 들어 3, 6, 9,,,
<2> 봉지의 무게가 5a+3b 의 형태가 아니다. 이 경우 -1을 출력하면 됨.
예를 들어, 7의 경우는, 5a+3b의 형태가 될 수 없다.
결과적으로 <1>의 경우를 먼저 다룬 다음, 이에 해당하지 않는 경우는 <2>에 해당하므로 -1을 출력하면 된다.
핵심 - 최대한 5로 나누면 된다.
문제에서 배달하는 봉지의 최소 개수를 출력하라고 한다.
이때 봉지의 무게를 최대한 5로 많이 나눌 때 배달하는 봉지의 최소 개수를 구할 수 있다.
예시 : <1> 의 1), 3)
예를 들어, 봉지 무게가 15다.
5로 나누면 3개이지만, 3으로 나누면 5개다.
즉, 최대한 5로 나눌 수록 봉지 개수가 최소가 된다.
즉, 1)이 3)의 경우보다 최소 봉지개수를 만들 수 있다.
예시 : <1>의 2), 3)
또 헷갈리는 경우가 있다.
18의 경우다.
이 수는, 5a+3b 형태도 된다. 15+3 으로, 5*3+3*1 형태가 된다.
즉, 2)의 경우에 해당.
그런데, 3의 배수이므로, 3*6 형태도 된다.
즉, 3)의 경우에도 해당.
그러면 이 두가지 경우 중 어느 경우로 계산해야 봉지의 최소 개수를 만들 수 있을까?
5a+3b 형태로 만들어야 한다.
이 경우는 봉지 개수가 4개이지만,
3b 형태로 만들면 봉지 개수가 6개 필요하다.
즉, 2)가 3)보다는 최소 봉지 개수를 만들 수 있다.
2)에 대한 자세한 설명
N(설탕 무게 ) = 5a+3b의 경우인데, 이때 a,b가 모두 1이상이다.
그렇기 때문에 N을 바로 5나 3으로 나눌 수 없어서, 먼저 N에서 5나 3을 뺀 수가 3이나 5로 나뉘는지 확인해야 한다.
예시 : N = 13
일단 N에서 3을 빼준다.
이때 N-3 = 10이므로 5로 나눌 수 있다. 즉 이 경우는 N=5*2 + 3*1 인 경우이다.
봉지의 개수(sum) 는 3을 하나 뺐으니 +1 하고, N-3 = 10= 5*2 이므로 +2 해줘서
최종적으로 3개 필요하다.
여기서 포인트는, N에서 3을 먼저 뺀 다음 그 수가 5의 배수로 나뉘는지 확인하는 것이다.
이와 반대로 N에서 5를 먼저 빼고 그 수가 3의 배수인지 확인하면 틀린다.
예시 : N =33 ( 3을 먼저 빼는 경우)
만약 33에서 3을 먼저 빼면 30이 된다. 그러면 이 경우 5로 나뉘기 때문에
sum = 1+6 = 7 , 즉 필요한 봉지 개수는 7개 이다.
예시 : N =33 ( 5를 먼저 빼는 경우)
33에서 5를 먼저 빼면 28이다. 이 경우 3으로 나뉘지 않으므로
5를 또 빼면 23이다. 3으로 나뉘지 않으므로
5를 또 빼면 18이다. 이 경우 3으로 나뉘므로
sum = 3 (5를 뺀 횟수) + 6(18/3) = 9가 된다. 즉 필요한 봉지 개수가 9로
위의 경우보다 더 많아졌음을 알 수 있다.
이렇게 생각해보면 결국, 1)과 2)의 경우에서도 1)의 경우가 2)보다 최소 봉지 개수를 만들 수 있음을 알 수 있다.
최종
설탕무게가 5a+3b 형태라면
1)의 경우를 먼저 고려해야 봉지의 최소 개수를 출력할 수 있다.
즉, 무게가 5로 나뉘면 그 값을 바로 출력해주고 끝내면 되고,
아니면
2)의 경우로 봉지 개수를 구한다음 출력해주면 된다.
이도 아니면
3)의 경우를 고려해서 봉지의 개수를 구한 다음 출력해주고 끝낸다.
그런데 1), 2), 3) 모두 해당하지 않는다면, 설탕 무게가 5a+3b 형태가 아닌 것이므로 -1 출력해주면 끝이다.
그래서 위의 순서대로 코드를 완성했다.