[C언어] 백준 2839번 설탕 배달

풀이방식1

#include <stdio.h>

int main(void)
{
	int N, a, n, found = 0; // 3 <= N <= 5000

	scanf("%d", &N);
	
	for (a = 0; !found; a++)
		if ((N + 2 * a) % 5 == 0)
		{
			n = (N + 2 * a) / 5;
			found = 1;
			if (n < a)
				found = 2;
		}

	printf("%d", found == 1 ? n : -1);

	return 0;
}

 

• a는 3kg 비닐백의 개수, n은 전체 비닐봉투의 개수이다.
• 3a + 5(n-a) == N를 만족하는 조합 중 a가 최소값을 가지는 조합이 가장 작은 n을 리턴할 것이다.
  • 3kg 비닐백을 적게 들고 5kg를 많이 들수록 전체 비닐백의 개수 n은 작아지기 때문에
  • 3kg비닐백의 개수를 나타낼 수 있는 변수를 만들고,
    for loop을 통해 a=0일 때부터 항등식을 만족하는 a, n의 값을 찾을 것이다.
• 3a + 5 (n-a) == N을 미지수 n을 기준으로 다시 쓰면 n = (N+2a)/5이다. (N과 a는 주어진다.)
  • 즉 (N+2a) / 5가 나머지를 가지지 않을 때 등식이 성립할 수 있고, 그때 전체 비닐백의 개수를 구할 수 있다.
  • flag variable "found"에 값을 할당하는데, 문제는 N + 2a % 5 == 0이라 할지라도, 논리적으로 말이 안되는 경우가 존재한다.
    • a는 flag를 바꾸지 않는 한 무한히 증가할 수 있는데, 전체 개수 n보다 3kg비닐백의 개수가 커질 수 있다.
      따라서 a값이 과도하게 커진다면 flag에 다른 값 2를 할당함으로써 반복문을 멈추고 출력을 진행해야 한다.

풀이방식2

#include <stdio.h>

int main(void)
{
	int n, m, r, found=0;

	scanf("%d", &n);

	if (n % 5 == 0)
		n = n / 5;
	else
		for (m = n / 5; !found && m >= 0; m--)
		{
			r = n - m * 5; 
			if (r % 3 == 0)
			{
				n = m + r / 3;
				found = 1;
			}
		}
	printf("%d", m < 0 ? -1 : n);

	return 0;
}

• 입력받은 n이 5로 떨어질때, 최소 비닐백 개수는 n/5이다
• 그렇지 않다면 nkg내에서 존재할 수 있는 5kg 비닐백의 최대 개수(m) n/5부터 시작해 나머지가 3kg로 떨어질 수 있는지 확인
• m이 음수가 되도록 찾지 못했다면, 3kg+5kg의 조합은 존재하지 않기 때문에 -1를 출력한다.