C언어 2839 설탕 배달 풀이

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

2839번: 설탕 배달

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

풀이

idea

1)규칙이 직관적으로 이해가지 않으므로, 귀납법을 이용한다.

 

2)x + y =n , 3<= 5x + 3y <= 5000을 그래프로 나타내어 구하기

-> 어떤식으로 코드를 짜야할지 감이 잡히지 않아 pass 

 

3)최소 봉지를 만들어야하므로, 최대로 나눠줘야함

-> 큰 수인 5를 기준으로 사고하기

 

 

귀납적으로 생각해보기

 

1) N = 15 일 때 

x	y
3	0

여기서 x =2 일때 x =1 일 때 불가능, x = 0일 때 y = 5라한다면 성립하지만 최소가 아니므로

x + y  = 3 즉 출력값은 3이다.

1) N = 16 일 때

x	y
2	2

x = 3 일 때  안된다.

x = 2 일 때 y =2 이면 가능하다.

따라서 x + y = 4 즉 출력값은 4이다.

 

이런식으로 귀납추론을 해보면, 도출하는 과정을 일반화 할 수 있다.

 

(1) 5로 나눠본다. --> 나누어 떨어지면, 거기서 끝 N = 15 의 경우

(2) 나누어 떨어지지 않는 경우, 그 나머지가 3으로 나누어 떨어지면, 거기서 끝 N = 16의 경우 

(3) 5로 나누어 떨어지지 않을 때, 그 나머지가 3으로도 나누어 떨어지지 않을 경우, 값을 도출할 수 없음. N = 4의 경우

 

따라서 이 과정을 코드화 시키면 정답을 도출할 수 있을 것이다.

 

정답코드

#include <stdio.h>
int main()
{
	int  N;
	scanf("%d", &N); //4
	int cnt = 0;
	
	if (N % 5 == 0) //아니므로 pass
	{
		cnt = cnt + N / 5;
		printf("%d", cnt);
		return 0;
	}
	else
	{
		int Q = N / 5;  //4 / 5 = 0 
		

		while (1)
		{
			if ((N - 5 * Q) % 3 == 0)   // 4 % 3 == 1
			{
				cnt = Q + (N - 5 * Q) / 3;
				printf("%d", cnt);
				return 0;
			}
			else
			{
				Q = Q - 1; // 
			}
			if (Q == -1) // x = 0 일 때 조차 안된 case이므로 -1
			{
				printf("-1");
				return 0;
			}
		}
	}
	
	return 0;
}

Q) int Q = N / 5 를 해준이유

  결국은 5로 나눈 몫을 기준으로 판단하는 것이기 때문

 

Q)(N - 5 * Q) % 3 == 0 이라는 조건과 Q = Q - 1

예를 들어 19라는 숫자를 대입했다고 하자.그럼 우리는 처음에 가장 큰 x 즉, x = 3 인경우부터 판단한다.x =3 일 때 , 5 * 3 + 3*y = 19 가 되고 3 * y = 19 - 15 를 만족하는 y 는 없으므로

이제, x = 2일때를 판단한다.

x =2 일 때, 5 * 2 + 3*y = 19가 되고

3 * y = 19 - 10 을 만족하는 y = 3 이다.

 

이 과정을 잘 살펴보면 x 즉 Q는 순차적으로 -1씩 감소하며 판단된다.

그리고 그에 따른 (N - 5 * Q)가 3으로 나눠지는 지 판단된다.

따라서 저런 코드를 입력한 것이다.

 

Q)if (Q == -1) 인 경우

예를들어 7을 떠올려보자, 앞서 살펴본 것과 같이

Q = 2일때 만족X

Q = 1일때 만족X

Q = 0 일 때조차 만족X

만족하지 못하는 Q는 이제 또 다시 -1이 되는데,

이 때가 우리가 x를 내림차순으로 다 판단했을 때이다.

따라서 판단가능한 x y 조합이 존재하지 않을 때이므로

-1을 출력하는 코드를 작성한 것이다.

 

+)그렇다면 왜 Q==0일때를 기준으로 하지 않았는가? 

Q == 0 일때는 아직 판단의 여지가 남아있는 상태이기 때문이다.

(4인 경우를 생각해보라) 

 

 

 

배운점

 

1)처음엔 x + y = n을 기준으로 코드를 짜려고 하였으나, x + y = 3 일 때와 x + y =5 일 때 등

 x =3 y=0 이거나 x= 0 y=5 일때 값이 15로 모두 동일해 계산하는데 중복이 생긴다.

 이런식으로 중복이 생기고 그것을 처리하는 것은 코드를 복잡하게 하므로, 일단 설계를 할 때 다른 방법은 없는지 

고민해보고 시작해야 한다. 컴퓨터의 기본 아이디어. 0/1

 

2)웬만하면 설계된 입력, 출력을 기준으로 생각하자.