[백준 12923번] 별 모으기 (C++)

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

좀 애먹은 문제다. 문제에서 주어지는 테스트 케이스가 간단해서 그런지 반례 상황을 생각못하고 여러번 틀리면서 찾았다. 

문제는 최소 클리어 횟수를 사용해서 스테이지의 모든 별들을 모으는 코드를 작성하라는 것이다.

---

아마 대부분 b를 오름차순으로 정렬해서 작은 b부터 얻을 수 있는 별들을 다 얻고 부족하면 먹을 수 있는 a로 별을 얻어서 b를 채우는 식으로 풀면 되겠다고 생각할 것이다.

하지만 a로 별을 얻을 때 어떤 스테이지 부터 먹어야 하는지 고민이 될 것이다.

 

코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <deque>
#define pii pair<int,int>
#define INF 1000000000
using namespace std;

bool compare(pii x, pii y){
	return x.second < y.second;
}

int main() {
	int n, a, b, star = 0, stageCnt = 0;
	deque<pii> info;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a >> b;
		info.push_back({a,b});
	}
    sort(info.begin(),info.end(),compare);
	while(!info.empty()){
		if(info[0].second <= star){
			star++;
			stageCnt++;
			if(info[0].first != INF) star++;
			info.pop_front();
		}
		else{
			int saveStar = star;
			for(int i = info.size()-1; i >= 0; i--){
				if(info[i].first <= star){
					info[i].first = INF;
					stageCnt++;
					star++;
					break;
				}
			}
			if(star == saveStar) {
				cout << "Too Bad";
				return 0;
			}
		}
	}
	cout << stageCnt;
}

 

 

---

[사고의 흐름]

1. 처음에는 코드를 잘못짜서 a를 먹을때마다 현재 별 개수를 증가해야 하는데 벡터를 한번 스캔하고 증가값을 한번에 올려서 답이 틀리는 경우를 발생시켰다. 

→ a로 스테이지를 깰때마다 star가 증가하게 수정

2. 해당 스테이지는 a를 먹었다는 것을 알기 위해서 먹고 나서 a값을 -1로 바꿔주었는데 애초에 if문을 검사할 때 a값이 현재 스타 개수보다 작아야 해서 한번 a를 클리어해도 계속 a를 클리어하면서 별을 먹을 수 있는 구조가 되버렸다.

→ 먹고 나서 바꾸는 값을 INF(매우 큰 값)로 바꿔서 해결

3. b를 먹지 못하기 때문에 a를 먹고 다시 b로 가야하는데, a를 먹는 순서에 고민이 있었는데 직관적으로 그냥 다시 a로 정렬해서 작은 a부터 먹으면 된다고 생각했는데 작은 것 부터 먹으면 안되는 케이스를 찾았다.

→ 근데 a가 큰거부터 먹도록 했는데 이 또한 잘못되었다.

4. a가 큰거부터 먹도록 하는게 아니라 b기준으로 정렬했을 때 뒤에서 부터 먹게 해야지 작은 b들이 a를 먹지 않고도 바로 클리어 할 수 있는 경우가 나와서 최소가 된다.

→ 끝

 

1,2 번은 구상한 것을 코드로 옮기면서 발생한 실수이고 로직 핵심은 4번인거 같다.

 

교훈: 메이플 쇼케이스 보면서 코딩하지 말자