[JAVA] 백준 2839번 설탕 배달 : 함수

2839번: 설탕 배달

 

1. 문제 추상화

 

3kg, 5kg 설탕봉지를 사용하여, 정확히 Nkg 설탕을 옮길 때, 봉지의 수를 최소화해라. 

 

2. 알고리즘 

 

3kg 봉지의 개수 : a

5kg 봉지의 개수 : b

옮겨야 할 설탕무게 : N (kg)

 

그러므로, 3a + 5b = N 이 성립한다.

a의 개수가 정해지면 b의 개수는 '자동으로' 정해진다. ( 함수 종속 )

 

N을 11이라 가정하자.

 

b가 0일때, a는 최대가 된다. 그러므로 0<= a <= 11/3 ( 3. xxx )

a는 정수이므로 0, 1, 2, 3이 범위에 포함된다. 

b는 a에 따라 값이 '자동으로'  정해지므로 b의 값을 정리하면 아래와 같다.

 

함수식 : 3a + 5b = 11 ( N ) ( 단, b는 정수여야 한다. )

a	0	1	2	3
b	정수 X	정수 X	1	정수 X

 

고로, a + b를 하면 3이다.

옮겨야 할 무게가 11kg일 때, 3kg 두 봉지, 5kg 1 봉지를 옮기면 되므로 총 3 봉지이다.

문제의 목적은 최소 봉지를 구하는 것이므로, a+b가 최소인 값을 반복문으로 구한다.

 

 

3. 코드

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int goal = sc.nextInt();
		
		int maxNumFor3kg = goal / 3; // 5kg 봉지의 개수가 0일때, 3kg의 최대 봉지 개수
		int numFor5kg = 0;
		int min = 5000/3; // 최소 봉지 개수 초기화
		
		
		for(int i=0; i <= maxNumFor3kg; i++) {
			if(( goal - 3*i ) % 5 == 0) { // 5kg 봉지의 개수가 정수인 것만 선별
				numFor5kg = ( goal - 3*i ) / 5;
				if( ( i + numFor5kg ) < min ) {
					min = i + numFor5kg; // 봉지 개수의 최소값 선별
				}
			}
		}
		
		if(min == 5000/3) {
			System.out.println(-1); 
		}else {
			System.out.println(min);
		}
	}
}