BaekJoon 2839 설탕배달

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

소스 결과 : 1984 KB / 0 ms

출처 : BackJoon / COCI 2010/2011 Contest #7 1번

 

설명

N kg의 설탕을 5 kg과 3 kg의 봉지에 나누어서 배달이 가능한지 묻는 문제

 

간단하게 생각해서 5로 나눈후 나머지가 3이면 가능하고 아니면 아닌 문제라고 생각했다가

틀린문제

 

N이 최대 5000, 5kg 으로 나누면 1000, 3kg로 나누면 1666.6번

최대로 돌려봐야 약 20만회 이기에 시간제한을 만족시킬 수 있다.

 

2중 for문을 사용하여 풀자

 

알고리즘

1. 0 에서 n 을 5로 나눈 몫 + 1 까지 반복 ( i )

 1-1 0 에서 n을 3으로 나눈 몫 + 1 까지 반복 ( j )

   1-1-1. i * 5 + j * 3 이 n 이면 i+j 를 현재 최소 봉지수와 비교, 작으면 최소 봉지수 = i + j

2. 출력

 

소스코드

#include <iostream>

using namespace std;

int main()
{
	int n;

	cin >> n;

	int min = 1667;

	for (int i = 0; i < n / 5 +1; i++)
	{
		for (int j = 0; j < n / 3 + 1; j++)
		{
			if (n == ((i * 5) + (j * 3)))
			{
				if (min > i + j)
					min = i + j;
			}
		}
	}

	if (min == 1667)
		cout << -1;
	else
		cout << min;

	return 0;
}