백준 : 2839번, 설탕 배달

문제 주소 : www.acmicpc.net/problem/2839

정답 비율 : 32.177% (2020.12.09 11:33 기준)

2839번: 설탕 배달

머리가 복잡해서 머리 식힐 김에 간단해 보이는 문제(문제 순위 26번 문제)를 골랐는데 푸는데 한 참 걸렸습니다.

 

문제 요약 : N이 주어지고 3 * x + 5 * y = N 일 때 x + y 의 최솟 값을 구하시오. (단, N을 만들 수 없으면 -1출력)

 

-> y가 클 수록 x + y의 값이 작아집니다.

 

-> 문제는 보다 싶이 아주 간단합니다. 순환 문만 사용할 줄 알면 되는 문제입니다. 시작 수를 i = n / 5 이고 범위는 0까지 감소하는 방향으로 순환문을 돌리면 풀리는 문제입니다.

 

코드는 다음과 같습니다.

#include<stdio.h>

int main(void)
{
	int num, i = 0, check = 1;
	scanf("%d", &num);
	
	for(i = num / 5; i >= 0; i--)
	{
		if((num - (5 * i)) % 3 == 0)
		{
			printf("%d\n", i + (num - (5 * i)) / 3);
			check = 0;
			break;
		}
	}
		
	if (check)
		printf("-1\n");
	return 0;
}

 

문제는 여기서에 순환 문을 사용하지 맙시다. 라는 문구를 넣으면 좀 많이 복잡해집니다. 모든 경우의 수를 계산해야합니다. 

-> N % 5 와 N % 3을 이용하여 어떻게든 규칙을 찾으려고 했습니다. 하지만 실패 그렇게 고민하다가 N % 10을 통하여 규칙을 찾게 됩니다.

 

모든 경우의 수 (범위 주의 : N >= 3) , k = N의 10의 자리수 

1. N % 10 == 0 (10, 20, ...) : 5의 배수이므로 N / 5가 최솟값이 되겠습니다.
2. N % 10 == 1 (11, 21, ...) : 1 + 5 = 6으로 3의 배수이므로 N / 5 - 1 + 6 / 3 = N / 5 + 1이 되겠습니다.
3. N % 10 == 2 (12, 22, ...) : 2 + 10 = 12으로 3의 배수이므로 N / 5 - 2 + 12 / 3 = N / 5 + 2이 되겠습니다.
4. N % 10 == 3 (03, 13, ...) : 해당 모든 수는 10 * k + 3 꼴이므로 N / 5 + 3 / 3 = N / 5 + 1이 되겠습니다.
5. N % 10 == 4 (04, 14, ...) : 조건부로 N >= 14일 때 5 + 10 * (k - 1) + 9 꼴이므로 (N - 14) / 5 + 5 / 5 + 9 / 3 = N / 5 - 14 / 5(=2) + 1 + 3 = N / 5 + 2 (N >= 14)이 되겠습니다.
   
   
6. N % 10 == 5 (05, 10, ...) : 5의 배우이므로 N / 5이 되겠습니다.
7. N % 10 == 6 (06, 16, ...) : 해당 모든 수는 10 * k + 6 꼴이므로 N / 5 - 1 + 6 / 3 = N / 5 + 1이 되겠습니다.
8. N % 10 == 7 (07, 17, ...) : 조건부로 N >= 12일 때 10 * (k - 1) + 5 + 12 꼴이므로 (N - 17) / 5  + 1 + 4 = N / 5 - 17 / 5(=3) + 5 = N / 5 + 2 (N >= 17)이 되겠습니다.
9. N % 10 == 8 (08, 18, ...) : 해당 모든 수는 10 * k + 3 + 5 꼴이므로 (N - 8) / 5 + 2 = N / 5 + 1
10. N % 10 == 9 (09, 19, ...) : 해당 모든 수는 10 * k + 9 꼴이므로 (N - 9) / 5 + 3 = N / 5 + 2 

이 처럼 모든 결과가 어떤 규칙이 있는 것을 확인 할 수 있습니다.

 

코드는 다음과 같습니다.

#include<stdio.h>

int main(void)
{	
	int num, tmp;
	
	scanf("%d", &num);
	
	tmp = num % 10;

	if (tmp == 0 || tmp == 5)
		printf("%d\n", num / 5);
	else if(tmp == 1 || tmp == 3 || tmp == 6 || tmp == 8)
		printf("%d\n", num / 5 + 1);
	else if((tmp == 2 || tmp == 4 || tmp == 7 || tmp == 9) && num >= 12)
		printf("%d\n", num / 5 + 2);
	else if(num % 3 == 0)
		printf("%d\n",num / 3);
	else
		printf("-1\n");
	return 0;
}

N / 5 + 2 같은 경우들을 보면 모두 조건부인데 그것의 최하 값이 N >= 12입니다. 

 

--> 사실 저 같은 경우에는 두 번째 풀이를 풀고 첫 번째 풀이로 풀었습니다.

--> 옆에 지나가던 친구가 슥 보더니 for 돌리면 되겠네 하기 전까지는 첫 번째 풀이는 생각도 못 했습니다. ㅎㅎ