[BOJ] 2839 설탕배달

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

Note

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;
}

2019-01-05 19:37:34에 Tistory에서 작성되었습니다.