[백준/C++] 27447 주문은 토기입니까?

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

27447번: 주문은 토기입니까?

 

한별이는 매시간마다 다음 중 하나의 일을 할 수 있다.

 

1. 토기를 만든다

2. 커피를 담는다

3. 서빙한다

 

이 일들은 시간과 횟수의 두 가지 관점에서 볼 수 있는데

 

1. 토기는 언제든 만들어도 되고 남아도 상관이 없다

2. 커피는 너무 일찍 담으면 흙탕물이 되므로 제한된 시간 내에 만들어야 한다

3. 서빙은 손님이 방문한 시간에 해야 하므로 고정되어 있다

 

그러므로 이 문제는 커피를 담는 시간을 정하는 문제라고 간단하게 정리할 수 있겠다.

 

코드 구현 과정 1

t[i] = i초에 일할 수 있나?

p = 방문 예정 손님

 

1. 현재 시간에 p의 커피를 담을 수 있다면 미리 서빙을 하고 다음 손님으로 넘어간다

    (t[p] = false, 서빙을 해야 되니 p초에는 일할 수 없는 것)

2. 남은 시간에는 토기를 만든다

 

* 종료 조건: p가 커피를 못 받았는데 시간이 지나가 버린 경우

* p <= t

 

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

using namespace std;

void input();
void solve();

int n, m;
bool t[1000001];
int pottery;
vector<int> people;
int coffee;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solve();

	return 0;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		people.push_back(p);
	}
}

void solve() {
	bool save = true;
	int p = 0;
	int cur = 0;
	int last = people[n - 1];
	for (int i = 0; i <= last; i++)
		t[i] = true;
	for (int i = 0; i <= last; i++) {
		if (t[i]) {
			if (cur < n)
				p = people[cur];
			if (p <= i) {
				save = false;
				break;
			}
			if (i + m >= p && pottery) { // 커피 담기
				pottery--;
				t[p] = false;
				cur++;
			}
			else
				pottery++;
		}
	}
	cout << (save ? "success" : "fail");
}

 

예전에 제출하고 틀려서 이게 아니구나 했던 코드였는데, 밑의 코드로 난수를 발생시켜서 비교해 보니 그냥 컴파일 오류였다... 손님을 다 서빙했는데 시간이 남은 경우, 없는 손님을 가리키려다 보니 인덱스 에러가 발생한 것이었다. 원래는 마지막 손님을 서빙함과 동시에 영업을 종료해야 하는데 미리 서빙하는 형태이다 보니 그게 아니어서 이렇게 된 것 같다.

 

코드 구현 과정 2

첫 번째 코드의 실패를 겪고 새로 구상한 코드.

손님을 기준으로 해서 커피를 담자!가 이 코드의 요약이다.

 

p = 방문 예정 손님

s = 실제로 방문한 손님

 

p를 기준으로 커피를 담되, 담은 커피를 실제로 수령하는 s를 두었다. 약간 투 포인터 느낌.

 

* 처음에는 커피의 개수를 저장하는 변수를 따로 만들지 않았는데 그러다 보니 조건만 맞으면 무조건 커피를 담게 되어서

* coffee 변수를 두어 손님의 수만큼만 커피를 담도록 했다

* 쓰다 보니 깨달았는데 손님에게만 흙탕물을 서빙하지 않으면 되는 거였... 커피는 많이 만들어도 상관없는 듯

* 그리고 해당 라인에는 오류가 있는데, 중간중간 커피를 가져가는 손님이 있으니까 i + 1 - s가 맞음

 

* 종료 조건: s가 왔는데 커피가 없는 경우

 

미리 만든 토기와 커피의 개수를 체크하면서 서빙한다는 점에서 이 코드가 뭔가 더 직관적이고 현실적인 것 같다. 종료 조건만 봐도 훨씬 깔끔하다!

 

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

using namespace std;

void input();
void solve();

int n, m;
int t = 0;
int pottery = 0;
vector<int> people;
int coffee = 0;
string ans = "success";

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solve();

	return 0;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		people.push_back(p);
	}
}

void solve() {
	int s = 0;
	int i = 0;
	int p = 0;;
	while (s < n) {
		if (i < n)
			p = people[i];
		if (t == people[s]) {
			if (!coffee) {
				ans = "fail";
				break;
			}
			s++;
			coffee--;
		}
		else if (p - m <= t && coffee < i + 1 && pottery) {
			coffee++;
			pottery--;
			i++;
		}
		else
			pottery++;
		t++;
	}
	cout << ans;
}