백준#2839

 

2839번은 수학적 사고가 필요한 문제인데요. 

5키로그램 봉지와 3키로그램 봉지를 잘 조합하여 최소한의 봉지수로 N킬로그램(input)을 나눠담는 문제입니다.

 

그렇기 때문에 5키로그램으로 먼저 나누고 안되면 3키로그램을 이용해야 하는데요. 즉, 15처럼 3으로도 나눠지고 5로도 나눠지는 수가 들어온다면 5킬로그램 3봉지로 표현해야 한다는 것입니다.

 

5로 나눌 수 없는 것을 3을 어떻게 조합하면 될지 생각해봅시다. 3*2인 6은 5로 나누면 나머지가 1입니다. 3*3인 9를 5로 나누면 나머지가 4입니다. 이를 이용해서 문제를 분석해볼까요? 영 모르겠는 문제를 만나면 종종 직접 적어보는 것도 나쁘지 않습니다. 

	숫자(N)	3	4	5	6	7	8	9	10
	봉지개수(5봉지수+3봉지수)	1	X	1	2	X	2	3	2
		1(0+1)		(1+0)	2(0+2)		2(1+1)	3(0+3)	2(0+2)
11	12	13	14	15	16	17	18	19	20
3	4(0+4)	3(2+1)	4(1+3)	3(3+0)	4(2+2)	5(1+4)	4(3+1)	5(2+3)	(4+0)

 

위의 표를 보면 5로 나누고 난 나머지를 처리하는 3킬로그램짜리 봉지의 개수가 4,1,3,0,2,4,1,3,0... 이런 식으로 주기가 나눠집니다. 하지만 5킬로그램짜리 봉지의 개수는 0,2,1,3,2,1,3,2,4...로 규칙성이 느껴지지 않습니다. 하지만 5킬로그램을 이용한 무언가 + 규칙성으로 문제를 풀 수 있지 않을까라는 생각을 할 수 있죠.

 

이 문제의 어려운 부분은 N/5 + 규칙 이라는 식을 찾아내기 어렵다는 점입니다.

import java.util.Scanner;
public class Main
{
   	public static void main(String[] args) {
	    Scanner in = new Scanner(System.in);
	    int x = in.nextInt();
	    if(x==4||x==7)  //더 큰 값에 있을 수도 있으려나??
	    {
	            System.out.println(-1);
	    }
	    else if(x%5==0){ //5로 나눈 나머지가 3으로 나누어 떨어짐
	        System.out.println(x/5+(x%5)/3);
	    }else if(x%5==1||x%5==3){
	        System.out.println(x/5+1);
	    }else if(x%5==4||x%5==2){
	        System.out.println(x/5+2);
	    }


	}
}

 

다음과 같은 방법으로도 풀 수 있습니다.

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 num = Integer.parseInt(br.readLine());
		
		int N = 0;
		
		while(true){
		if(num%5 == 0) {
			N += num/5;
			break;
		}
		
		num -= 3;
		N++;
		
		if(num < 0) {
			N = -1;
			break;
		}
        System.out.println(N);
	}
		
}