백준 2839번
https://www.acmicpc.net/problem/2839
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다.
만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
생각하기
문제에서 반복되는 규칙을 찾는건 범위가 너무 넓다고 생각해서
낮은 숫자의 범위를 거를 수 있는 적절한 방법을 찾는 게 쉽겠다고 생각을 했다.
일단 처음에 5의 배수는 무조건 바로 출력하는 것,
5의 배수로 나올 수 있는 봉지 수는 볼 것도 없이 최소의 봉지 수가 된다.
높은 숫자의 단위는 오히려 쉬웠다.
4999를 숫자를 예로 들어서 얘기를 해보자면, 4999를 5로 나눠서 정수로 나타내면 999가 나오게 된다.
여기서 우리는 최소의 봉지 숫자를 구해야 하므로 5kg의 봉지로 가장 많이 들 수 있는 봉지 수가 최소의 봉지 숫자가 된다는 것을 알 수 있다.
그렇다면 999부터 1까지 내려가면서 5키로 봉지에 설탕을 담으면서 나머지 값이 3의 배수로 나오게 되면 그 봉지의 숫자가 최소의 봉지수 값이 되는 것이다.
999 * 5 = 4995가 된다. 4999 - 4995는 4가 되기 때문에 3으로 나눠지지 않는다.
이제 다음 999 값을 하나 줄여서 998 * 5로 4990 값을 얻을 수 있다.
4999 - 4990의 값은 9 이므로 3의 배수 값을 얻을 수 있다.
이렇게 되면 5kg의 봉지로 998개와 3kg의 봉지 3개로 총 1001개의 봉지가 4999kg의 설탕을 나누어 담을 수 있는 최소값이라는 결과를 얻을 수 있다.
이제 낮은 숫자의 단위가 문제였는데,
3의 배수 {3, 6, 9} -1을 출력해야하는 {4, 7}, 그다음 11과 12
해당 테스트 케이스 값이 가장 까다로웠다.
하나의 값을 처리하면 다른 값이 제대로 나오지 않는 문제가 자꾸 생겨서,
결국 이문제를 푸는데 하루를 넘겨버렸다..
시간이 오래 걸려서 나름의 거름망을 찾는 데 성공했다
먼저 N에서 5를 뺀 값을 minus_five 변수에 저장하고
N에서 5를 나눈 값을 div_five 변수에 저장했다.
minus_five에서 2보다 작거나 같은 수들은 3, 5, 6, 7에 해당한다.
먼저 여기에 해당하는 값들은 따로 3의 배수로 검사하고 3의 배수가 아닌 값들은 -1을 출력하도록 했다.
그다음 else 부분에서는 위에서 말한것 과 같이 큰 수를 찾는 방법으로 div_five 값 만큼 반복한다.
여기서 만약 i 값이 1이 됐을 경우는 12의 경우에 해당하는데
else if(i==1) 로 들어가서 3의 배수인지 체크하게 되고 아닐 경우 -1의 값을 출력하게 된다.
TMI
상근이는 몇개의 직업을 가진걸까?..
설탕 배달도 해야되고.. 나무도 잘라야되고..
제발 상근아 니 일은 니가 직접해라
한대 맞기 전에..
코드
import java.io.*; 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()); if(N % 5 == 0) { System.out.println(N / 5); } else { int div_five = N / 5; int minus_five = N - 5; if(minus_five <= 2) { if(N % 3 == 0) { System.out.println(N / 3); } else { System.out.println(-1); } } else { for(int i=div_five; i>=1; i--) { int count = i; int mod = N - (i * 5); if(mod % 3 == 0) { count += mod / 3; System.out.println(count); break; } else if(i == 1) { System.out.println(N / 3); } } } } } }
