[문제] 백준 2839번 설탕 배달

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

 

풀이

 

1. 첫번쨰 풀이

5의 배수를 기준으로 잘라서 나열해보자.

첫 행은 무게고, 아래 순서쌍은 (3kg 봉지 개수, 5kg 봉지 개수)이다.

3	4	5
(1,0)	X	(0, 1)

6	7	8	9	10	11	12	13	14	15
(2,0) -> 2	X	(1,1)-> 2	(3,0)-> 3	(0,2)->2	(2,1)->3	(4,0)->4	(1,2)->3	(3,1)->4	(0,3) ->3

16	17	18	19	20	21	22	23	24	25
(2,2) -> 4	(4,1) -> 5	(1,3)-> 4	(3,2)->5	(0,4) -> 4	(2,3)-> 5	(4,2) -> 6	(1,4)->5	(3,3) -> 6	(0,5)->5

위와 같이 나열해서 알 수 있는 사실은

1. 4와 7만 무게를 만들 수 없다.

2. 5의 배수는 5를 나눈 값이 봉지의 개수다.

3. 5의배수 +1과 5의 배수+3의 값은 동일하고, 이는 5를 나눈 값과 같다. (또는 자신보다 작은 5의배수 나눈 값 +1)

4. 5의 배수+2와 5의 배수 +4의 값은 동일하고, 이는 5를 나눈 값 + 1과 같다. (또는 자신보다 작은 5의 배수를 나눈 값 +2)이다.

public class BOJ_2839 {
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		int a = 0, b= 0;	// 3kg 봉지, 5kg 봉지
		int ans = 0;
		if(N == 4 || N == 7) {
			System.out.println(-1);
			return;
		}
		if(N==3) {
			System.out.println(1);
			return;
		}
		if(N%5 ==0) {
			ans = N/5;
		}else if(N%5==1 || N%5 == 3) {
			ans = N/5+1;
		}else if(N%5 ==2 || N%5 == 4) {
			ans = N/5+2;
		}
		System.out.println(ans);
	}
}

2-1. 두번째 풀이

 

1. 무게가 5의 배수라면 봉지의 개수는 무게/5

2. 5의 배수가 아니면 3을 계속 빼주면서 카운트 한다.

int N = Integer.parseInt(in.readLine());
int count = 0;
while(true) {
	if(N % 5 == 0) {
		count += N/5;
		break;
	}
	N -= 3;
	count++;
	if(N<0) {
		count--;
		break;
	}
 }

2-2.

 

int N = Integer.parseInt(in.readLine());
int cnt = 0;

while(N>2) {
	if(N % 15 == 0) {
		N -= 15;
		cnt +=3;
	}
	else if(N%3 == 0) {
		N -= 3;
		cnt++;
		}else {
			N -=5;
			cnt++;
    }
}
if(N != 0)
	System.out.println(-1);
else
	System.out.println(cnt);