[BOJ] 2839번 : 설탕 배달 (C언어)

1. 문제

2839번: 설탕 배달

1. 설탕 N kg을 배달하고자 한다.
2. 3kg, 5kg 봉지를 이용해서 배달한다.
3. 최소 봉지 개수 구하기
4. 불가능한 경우 -1 출력

2. 알고리즘

1. 그리디

2. 3, 5는 배수관계가 아니다.

3. 3만 가능한 경우의 수를 구한다.

   → 3, 6, 9, 12

4. 5로 최대한 뺀 후 3, 6, 9, 12가 나오면 멈춘다.

5. 4, 7인 경우 불가능

3. 소스코드

#include <stdio.h>

int main() {
	int n = 0;
	scanf("%d", &n);
	
	if(n == 4 || n == 7)
	    printf("%d", -1);
	else{
	    int count = 0;
	    while(1){
	        if(n == 0 || n == 3 || n == 6 || n == 9 || n == 12){
	            printf("%d", count + n / 3);
	            break;
	        }
	        n -= 5;
	        count += 1;
	    }
	}
	
	return 0;
}

먼저 4, 7이면 불가능하므로 -1을 출력한다. 이를 제외한 경우에 n에서 5를 계속해서 빼다가 0, 3, 6, 9, 12가 나오면 멈춘다.

4. 발전

#include <stdio.h>

int main() {
	int n = 0;
	scanf("%d", &n);
	
	if(n == 4 || n == 7)
	    printf("%d", -1);
	else if(n % 5 == 1 || n % 5 == 3)
	    printf("%d", n / 5 + 1);
	else if(n % 5 == 2 || n % 5 == 4)
	    printf("%d", n / 5 + 2);
	else
	    printf("%d", n / 5);
	
	return 0;
}

5를 계속해서 빼는 것은 시간복잡도 관점에서 굉장히 안 좋다. 그러므로 n을 5로 나누고 나머지가 3, 6, 9, 12인 경우에 대해서 한번에 연산하는 것으로 바꿀 수 있다. 이때 6, 9, 12 같은 경우에는 나머지가 1, 4, 2로 체크하면 된다.

• 나머지가 1인 경우에는 5kg 봉지 하나를 빼서 6kg을 3kg 봉지 2개로 사용하는 것으로 봐서 (n / 5) - 1 + 2로 생각할 수 있다.
• 나머지가 2인 경우에는 5kg 봉지 2개를 빼서 12kg을 3kg 봉지 4개로 사용한다. 따라서 (n / 5) - 2 + 4가 된다.
• 나머지가 3인 경우에는 3kg 봉지 1개를 추가한다. 그러므로 (n / 5) + 1이 된다.
• 나머지가 4인 경우에는 5kg 봉지 1개를 빼서 9kg을 3kg 봉지 3개로 사용한다. 즉, (n / 5) - 1 + 3이 된다.

위 코드에 경우에는 C언어 자체과 굉장히 빠른 언어이기 때문에 두 코드의 시간차이가 크지 않지만 파이썬으로 반복문으로 풀 경우 시간초과가 발생한다.