[백준/BOJ] 2839번 설탕 배달 (C/C++)

백준 온라인 저지(BOJ) 2839번 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

* 사용언어 : C언어, C++

 

1. 문제

설탕 N킬로그램을 배달 (3 ≤ N ≤ 5000)

3킬로그램과 5킬로그램 봉지가 있음

최대한 적은 개수의 봉지로 배달하려 함

 

봉지의 최소 개수를 출력

(정확하게 N킬로그램이 안된다면 -1 출력)

 

2. 풀이

BOJ 단계별로 풀어보기를 순서대로 해결했다면, 처음으로 만나는 알고리즘 구현 문제입니다.

복잡해보이지만, 규칙을 찾는다면 어렵지 않게 풀 수 있습니다.

 

봉지를 최소로 사용하려면 5킬로그램 봉지를 최대한 많이 사용해야합니다.

5 단위 주기로 규칙이 있을 것이라 가정하고 3부터 19까지 봉지 최소 개수를 확인해보았습니다.

 

(n : 설탕의 총 무게, count : 봉지 최소 개수)

 

정확하게 만들 수 없는 4킬로와 7킬로 제외하고 보면,

5개 주기로 값이 반복되고 있습니다.

n = 5, 10, 15 (n % 5 == 0) 의 count 값은 n / 5 와 같습니다.

n = 6, 11, 16 (n % 5 == 1) 그리고 8, 13, 18 (n % 5 == 3) 의 count 값은 n / 5 에 1을 더한 값과 같습니다.

n = 12, 17 (n % 5 == 2) 그리고 9, 14, 19 (n % 5 == 4) 의 count 값은 n / 5 에 2를 더한 값과 같습니다.

 

이러한 규칙을 활용하여 코드를 작성했습니다.

 

* switch문에서 아래와 같이 작성하면, 1과 3인 경우 해당 실행문이 실행됩니다.

case 1:
case 3:
	// 실행문

 

3. 코드

#include <stdio.h>

int main() {
	int n, count;
	scanf("%d", &n);

	if (n == 4 || n == 7) {
		printf("-1\n");
		return 0;
	}

	count = n / 5;
	switch (n % 5)
	{
	case 0:
		printf("%d\n", count);
		break;
	case 1:
	case 3:
		printf("%d\n", count + 1);
		break;
	case 2:
	case 4:
		printf("%d\n", count + 2);
		break;
	}
	return 0;
}