설탕배달(2839)
문제정보
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
해설
원래라면 모든 경우의 수를 구하고 그중 가장 작은 수를 선택하는 방향으로 해도 된다.
5가 1부터 N/5까지, 그중에 3이 1부터 N/3까지
만약 N이 5000이면 1000 * 1666번이 된다. 이 횟수는 시초가 안나는 횟수라 실행해도 상관 없다.
하지만 우리가 단순히 문제를 푸는게 아니라 여기서 무언가를 배워간다면 문제가 우너하는 풀이 방향을 이해해야 한다.
만약 30이라는 숫자가 있을때 3으로 나누는 것보다 5로 나누는 것이 더 적은 횟수가 든다.
따라서 5를 우선으로 나눠야 하며, 이후 3으로 나누는 것이 효율적이다.
각 5와 3으로 나누었을때의 횟수들을 표로 작성하면
위와같은 그림이 나온다.
이후에 5가 하나일때는
이를 반복하면
이러한 식이 되는데 지금 보면 최솟값에 무언가 규칙이 있다는것을 알 수있다.
예를 들어 4와 7을 제외하고 5의 N배수마다 N, N+1, N+2, N+1 N+2 로 반복되는 것을 알 수 있다.
왜 이런 형태가 반복될까?
이는 위에 말한 가장 큰 5로 나누는 것인데,
보다시피 5에서 10이 되려면 5만 더해지면 되기 때문에 5의 최소값인 1에 1을 더하기만 하면 된다. 6도 마찬가지로 11까지 최소값이 1더해지는데 이후에 11에서 16, 16에서 21 이런식으로 1씩 증가하게 된다.
따라서 1씩 증가되는 같은 패턴을 보이는데 여기서 7은 3과 5로 만들수 없지만 12는 3을 4개로 만들 수 있기 때문에 그 이후에 값을 채우게 되면 N, N+1, N+2, N+1 N+2의 패턴을 가지게 된다.
코드
- 입력을 받는다.
- N을 5로 나누어 나머지로 N이 5의 배수인지 확인한다.
- 5의 배수면 나머지 몫 answer변수에 집어넣는다.
- N이 4또는 7인지 확인한다.
- 4또는 7이면 표현 불가이기때문에 answer변수에 -1집어 넣는다.
- N을 5로 나누고 몫을 answer변수에 더한다.
- 5로 나눈 나머지를 3으로 나누고 몫을 answer변수에 더한다.
- 5로 나눈 나머지를 3으로 나누고 나머지를 answer 변수에 더한다.
- answer 출력 끝.
N, N+1, N+2, N+1 N+2 이 패턴을 공식화 한게 4번이다.
package 알고리즘스터디.수학;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class _2893 {
// 설탕 배달
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int answer = 0;
if(N%5 == 0){
answer = N/5;
}else if(N == 4 || N == 7){
answer = -1;
}else{
answer += N/5;
answer += (N%5)/3;
answer += (N%5)%3;
}
System.out.println(answer);
}
}
사실 그냥 5로 나누고 3으로 안나눠지면 5의 개수를 하나씩 줄여가면서 3으로 나누는 방법이 미세하게 빠르다.
왜냐하면 어떤 숫자가 나오건 최소 4번안에 정답이 나오기 때문이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
// 설탕 배달
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int five = N/5;
int three = (N%5)/3;
while(N%((five*5) + (three*3)) != 0){
five--;
if(five == 0){
three = N/3;
}else{
three = (N-(five*5))/3;
}
if(five < 0){
break;
}
}
if(five < 0){
System.out.println(-1);
}else{
System.out.println(five + three);
}
}
}