[BOJ/20956] 아이스크림 도둑 지호, c++

www.acmicpc.net/problem/20956

20956번: 아이스크림 도둑 지호

한줄 후기 : 백준에도 드디어 오마이걸이.. 기뻐하는 미라클 

요새 졸업작품 때문에 백준은 거의 안들어가는데 한번 들어갔다가 '지호'를 보고 멈칫..

집에서 한번 풀어보았다.

문제는 처음에 살짝 복잡했는데 요약하자면 지호가 아이스크림을 먹을 때 가장 양이 많은 것을 왼쪽에서 부터 먹는다. 이때 양이 7의 배수인 아이스크림은 민트 초코로 이를 먹으면 지호가 화가나서 아이스크림을 좌 우로 뒤집는다. 

이제 M개만큼 아이스크림을 먹는 순서를 출력하면 된다.

 

근데 지호 민트초코 싫어하니.. 난 좋아하는데

 

무튼.. 처음에 시도한 방법은 먼저 정렬을 한 후 두개의 벡터를 만들어 하나는 왼쪽에서 부터, 다른 하나는 같은 양일 때는 무조건 오른쪽 부터 나오도록 했다. 그리고 변수를 이용해 출력하는 방법인데 내가 생각한 예제는 다 맞았지만 틀렸다. 

다른 방법으로 접근해 보았는데 deque을 이용해 보았다.

사실 이 문제는 결국 양이 큰 아이스크림은 생각할 필요가 없이 그냥 먹으면 된다. 문제는 같은 양일때인데 양이 같으면 혹시나 민트초코를 먹었을 때 순서가 바뀌기 때문에 고려해주어야한다.

즉, 덱을 사용한다면 그냥 뒤집히지 않았을 때는 front, 뒤집혔을때는 back에서 빼주면 되는 것이다.

 

그런데 틀렸다. 나의 논리로는 절대 틀리지 않았는데..

 

//WA
//BOJ 20956 아이스크림 도둑 지호

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

vector<pair<int, int> > v;
deque<pair<int, int> > dq[101010];

bool cmp(const pair<int, int> &a, const pair<int, int> &b){
	return a.first > b.first;
}

int main(){
	int N, K, t;
	scanf("%d %d", &N, &K);
	for(int i=1; i<=N; i++){
		scanf("%d", &t);
		v.push_back({t, i});
	}
	int idx = 0, prev;
	sort(v.begin(), v.end(), cmp);
	dq[0].push_back({v[0].first, v[0].second});
	prev = v[0].first;
	for(int i=1; i<N; i++){
		if(v[i].first == prev){
			dq[idx].push_back({v[i].first, v[i].second});
			prev = v[i].first;
		}
		else{
			idx += 1;
			dq[idx].push_back({v[i].first, v[i].second});
			prev = v[i].first;
		}
	}
	idx = 0;
	int ck = 0, cur = 0, fir, sec; // ck == 0 이면 7의 배수 아닌 상태 앞에서 빼기 , ck == 1 뒤집힌 상태 뒤에서 빼야함
	while(K--){
		if(!ck){
			if(dq[idx].size() > 0){
				fir = dq[idx].front().first;
				sec = dq[idx].front().second;
				printf("%d\n", sec);
				dq[idx].pop_front();
			}
			else{
				idx += 1;
				fir = dq[idx].front().first;
				sec = dq[idx].front().second;
				printf("%d\n", sec);
				dq[idx].pop_front();
			}
			if(fir % 7 == 0){
				ck = 1;
			}
			continue;
		}
		else{
			if(dq[idx].size() > 0){
				fir = dq[idx].back().first;
				sec = dq[idx].back().second;
				printf("%d\n", sec);
				dq[idx].pop_back();
			}
			else{
				idx += 1;
				fir = dq[idx].back().first;
				sec = dq[idx].back().second;
				printf("%d\n", sec);
				dq[idx].pop_back();
			}
			if(fir % 7 == 0){
				ck = 0;
			}
		}
	}
	return 0;
}

 10%에서 틀렸고, 도저히 반례가 생각나지 않아 질문을 올렸는데

세상엔 똑똑한 분들이 많다.

그렇다.. 나는 순서를 고려하지 않고 정렬하고 있었다!! 즉 같은 양일 때 뒤에 있는 아이스크림이 먼저 올 수도 있었다. 

그래서 바로 cmp 함수를 수정해주었다. 결과는 AC!! 

//AC
//BOJ 20956 아이스크림 도둑 지호

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

vector<pair<int, int> > v;
deque<pair<int, int> > dq[101010];

bool cmp(const pair<int, int> &a, const pair<int, int> &b){
	if(a.first == b.first){
        return a.second < b.second;
    }
    return a.first > b.first;
}

int main(){
	int N, K, t;
	scanf("%d %d", &N, &K);
	for(int i=1; i<=N; i++){
		scanf("%d", &t);
		v.push_back({t, i});
	}
	int idx = 0, prev;
	sort(v.begin(), v.end(), cmp);
	dq[0].push_back({v[0].first, v[0].second});
	prev = v[0].first;
	for(int i=1; i<N; i++){
		if(v[i].first == prev){
			dq[idx].push_back({v[i].first, v[i].second});
			prev = v[i].first;
		}
		else{
			idx += 1;
			dq[idx].push_back({v[i].first, v[i].second});
			prev = v[i].first;
		}
	}
	idx = 0;
	int ck = 0, cur = 0, fir, sec; // ck == 0 이면 7의 배수 아닌 상태 앞에서 빼기 , ck == 1 뒤집힌 상태 뒤에서 빼야함
	while(K--){
		if(!ck){
			if(dq[idx].size() > 0){
				fir = dq[idx].front().first;
				sec = dq[idx].front().second;
				printf("%d\n", sec);
				dq[idx].pop_front();
			}
			else{
				idx += 1;
				fir = dq[idx].front().first;
				sec = dq[idx].front().second;
				printf("%d\n", sec);
				dq[idx].pop_front();
			}
			if(fir % 7 == 0){
				ck = 1;
			}
			continue;
		}
		else{
			if(dq[idx].size() > 0){
				fir = dq[idx].back().first;
				sec = dq[idx].back().second;
				printf("%d\n", sec);
				dq[idx].pop_back();
			}
			else{
				idx += 1;
				fir = dq[idx].back().first;
				sec = dq[idx].back().second;
				printf("%d\n", sec);
				dq[idx].pop_back();
			}
			if(fir % 7 == 0){
				ck = 0;
			}
		}
	}
	return 0;
}

 

 

결론은 지호가 나와서 재밌는 문제 ㅎㅎ