[BOJ/Gold 5] 백준 19940 피자 오븐(C++)

문제 링크

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

19940번: 피자 오븐

문제

피자를 굽는 전자식 오븐이 있다. 이 오븐에 재료는 넣고 정확히 N분 동안 동작을 시키고자 한다. 그런데 이 오븐에 준비된 버튼은 아래와 같은 동작을 하는 5가지이다. 즉, 각각의 버튼은 동작 시간을 추가시키거나 감소시킨다. 처음에 피자 오븐의 첫 시간은 0분으로 정해져 있다. 시간을 감소시키는 버튼을 눌러서 시간이 0분보다 작아지는 경우에는 0분으로 설정된다. t가 현재 오븐에 세팅된 시간, t′은 버튼을 누른 뒤의 시간을 의미할 때, 각 버튼은 다음과 같은 기능을 가지고 있다.

• ADDH: t′=t+60
• ADDT: t′=t+10
• MINT: t′=t−10
• ADDO: t′=t+1
• MINO: t′=t−1

예를 들어, 58분을 설정하고 싶으면, ADDO (+1분) 버튼을 58번 눌러도 된다. 하지만, ADDH (+60분) 버튼을 한 번 누른 뒤에 MINO (-1분) 버튼을 2번 누르면 3번의 작업으로 58분을 만들 수 있다. 42분을 설정하고 싶은 경우에는 버튼을 ADDH, MINT, MINT, ADDO, ADDO 순서로 5번 눌러서 만들 수 있다. ADDT, ADDT, ADDT, ADDT, ADDO, ADDO 순서로 6번 눌러서 만들 수 있지만, 버튼은 최소 횟수로 누르려고 한다.

설정해야 할 시간이 주어졌을 때, 그 시간을 만들기 위해 눌러야 하는 버튼의 최소 횟수와 그 방법을 구하는 프로그램을 작성하시오.

입력

입력을 T개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 설정해야 하는 시간 N이 분 단위의 정수로 주어진다.

출력

각각의 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해서 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해서 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수를 출력한 것이다. 최소 횟수로 누르는 방법이 여러가지인 경우에는 사전 순으로 가장 앞서는 방법을 출력한다.

작업 횟수가 동일한 방법이 여러가지가 있을 때, ADDH를 누르는 횟수가 적은것이 사전 순으로 앞서는 것이고, ADDH를 누르는 횟수가 동일하면, ADDT를 누르는 횟수가 적은것이 먼저이다. ADDT를 누르는 횟수가 동일하면 MINT를 누르는 횟수가 적은것이, MINT를 누르는 횟수가 동일하면 ADDO를 누르는 횟수가 적은것이, ADDO를 누르는 횟수가 동일하면 MINO를 누르는 횟수가 적은것이 사전 순으로 앞서는 것이다.

제한

•  1≤T≤100
•  1≤N≤10,000,000

예제 입력 1

3
5
12
27

예제 출력 1

0 0 0 5 0
0 1 0 2 0
0 3 0 0 3

알고리즘 분류

• 그래프 탐색
• 그리디 알고리즘

풀이

일단 60분이 넘어간다면, 최대한 ADDH만을 사용해서 60분 단위로 올려줘야 최대한 적은 횟수로 버튼을 누를 수 있다. 따라서 주어진 시간 N을 일단 60으로 나눈다. 그러면 N/60은 ADDH를 누른 횟수가 되는 것이고, 이제 우리는 N%60분을 5가지의 버튼을 사용해서 맞춰주면 된다.

또한 1분에서 59분까지의 버튼을 누르는 방법을 BFS를 사용해서 미리 구해두었다. 

사전 순으로 앞서는 방법을 출력하는 것이기 때문에 BFS 과정에서 큐에 구조체를 push할 때 MINO 버튼이 1 증가했을 때의 데이터부터 push해야 한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 65
#define LL long long
#define INF 2e9

using namespace std;
struct INFO {
	int ADDH, ADDT, MINT, ADDO, MINO, Time;
};

int T, N;
INFO Minute[MAX];
bool visited[MAX];
queue<INFO> Q;

void BFS() {
	INFO Info = { 0,0,0,0,0,0 };
	Q.push(Info);

	while (!Q.empty()) {
		INFO CurInfo = Q.front();
		Q.pop();

		if ((CurInfo.Time >= 0) && (CurInfo.Time <= 60) && (!visited[CurInfo.Time])) {
			visited[CurInfo.Time] = true;
			Minute[CurInfo.Time] = CurInfo;
			Q.push({ CurInfo.ADDH,CurInfo.ADDT,CurInfo.MINT,CurInfo.ADDO,CurInfo.MINO + 1,CurInfo.Time - 1 });
			Q.push({ CurInfo.ADDH,CurInfo.ADDT,CurInfo.MINT,CurInfo.ADDO + 1,CurInfo.MINO,CurInfo.Time + 1 });
			Q.push({ CurInfo.ADDH,CurInfo.ADDT,CurInfo.MINT + 1,CurInfo.ADDO,CurInfo.MINO,CurInfo.Time - 10 });
			Q.push({ CurInfo.ADDH,CurInfo.ADDT + 1,CurInfo.MINT,CurInfo.ADDO,CurInfo.MINO,CurInfo.Time + 10 });
			Q.push({ CurInfo.ADDH + 1,CurInfo.ADDT,CurInfo.MINT,CurInfo.ADDO,CurInfo.MINO,CurInfo.Time + 60 });
		}
	};
}

int main() {
	FIRST
	BFS();
	cin >> T;
	while (T--) {
		cin >> N;
		int M = N / 60;
		int R = N % 60;
		cout << Minute[R].ADDH + M << " " << Minute[R].ADDT << " " << Minute[R].MINT << " " << Minute[R].ADDO << " " << Minute[R].MINO << "\n";
	};

	return 0;
}