C++ / 2839 / 설탕 배달 ( 그리디 알고리즘 )

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

문제 요약

설탕 N 킬로그램을 배달해야합니다. 

설탕은 봉지에 담겨져 있습니다. 봉지는 3킬로그램과 5킬로그램 봉지가 있습니다.

최대한 적은 봉지를 들고 가려 합니다.

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

문제 풀이

1. n을 입력받습니다.

2. n * n 만큼 돌아가는 반복문을 만듭니다.

3. 바깥 반복문은 5키로그램 체크 안쪽 반복문은 3키로그램 채크입니다.

4. 5키로그램 갯수당 3키로그램 봉투가 몇개 들어가는지 합을 구합니다.

5. 그 합이 기존에 더했던 합보다 작을 경우 새로 갱신해줍니다.

6. cnt를 출력합니다.

주의할 점

가장 적은 횟수를 출력해야 하기 때문에 비교 조건에 기존값과 비교하는 내용을 꼭 넣어줘야합니다.

코드

#include<iostream>

using namespace std;

int n;
int cnt = -1;
int mn = 1234897;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i * 5 + j * 3 == n && mn > i + j)
			{
				mn = i + j;
				cnt = i + j;
			}
		}
	}
	cout << cnt;
	return 0;
}

반응형

예제1

18

결과1

예제2

4

결과2

예제3

6

결과3

예제4

9

결과4

예제5

11

결과5