C++ / 10162 / 전자레인지 ( 그리디 알고리즘 )

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

문제 요약

3개의 시간 조절용 버튼 a, b, c가 달린 전자레인지에서 시간 t를 입력받아 최소한으로 버튼을 눌러 t 시간을 맞춰야 합니다.

각각의 버튼들에 지정되어 있는 시간은a = 5분b = 1분c = 10초입니다.

 

문제 풀이

1. t 를 가장작은 버튼인 c와 나눌 수 없으면 리턴합니다. a와 b도 결국 10의 배수이기 때문에 c ( 10 )으로도 안나눠지는거면 기존 버튼으로는 완성할 수 없는 수 입니다.

2. 버튼을 큰 순으로 나눠지면 나눈 횟수를 각각 저장합니다.

3. 나눈 나머지를 t에 다시 저장하여 다음 버튼에서도 적용되게 합니다.

주의할 점

-1이 출력되는 조건을 간략화 할 때 버튼들이 결국 10의 배수라는 점이 중요합니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int t, a = 300, b = 60, c = 10, cnt = 0, aa =0, bb = 0, cc =0;
vector<int> p;

int  main()
{
	cin >> t;

	// 버튼으로 못맞추는 시간이면 리턴
	if (t % c != 0)
	{
		cout << -1;
		return 0;
	}


	if (t >= a)
	{
		aa = t / a;
		t = t % a;
	}
	if (t >= b)
	{
		bb = t / b;
		t = t % b;

	}
	if (t >= c)
	{
		cc = t / c;
		t = t % c;
	}

	cout << aa << " " << bb << " " << cc;
	return  0;
}

반응형

예제 1

100

결과 1

예제 2

189

결과 2