[백준 2336] 굉장한 학생

 내가 한 실수를 반복하지 않기 위해 기록해둔다... 후 너무 창피...

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

2336번: 굉장한 학생

문제 해설을 하자면 N명의 학생의 3개의 시험 등수를 준다. 이때 A가 B보다 3개의 시험 모두 등수가 높다면 A는 B보다 대단한 학생이 된다. 만약 A가 모든 학생들보다 3개의 시험 등수가 싹다 높다면 A는 굉장한 학생이 된다. 

알고 싶은 값은 굉장한 학생 수를 찾아오면 된다.

 

 일단 이렇게 3개의 차원의 값이 있다면 하나를 없애고 생각하는게 답을 찾아가는 공식이다. 거의 대부분 이 접근이 유리하다. 없애는 방법은 대게 정렬이 거의 쓰인다. 그럼 첫번째 셤을 기준으로 정렬을 해버린다. 그렇게 되면 가장 맨 먼저 오는 학생은 무조건 굉장한 학생 중 한명이다. 왜냐면 첫 번째 셤 등수로 다른 모든 학생에게 남부끄럽지 않는 비장의 무기가 된다. 즉, 최소 하나의 셤 점수가 남들보다 무조건 높으니 굉장한 학생이 된다. 물론 다른 셤에서 1등을 한 학생들 도 마찬가지.

 이렇게 되면 이 정렬 순서대로, i번째 학생은 내 이전에 탐색된 모든 학생들 중 한명이라도 두 번째, 세 번째 셤 등수가 둘 다 나보다 낮다면, i번째 학생은 굉장한 학생에 끼지 못한다. 왜냐면 나보다 대단한 학생이 있으니깐!

 그렇기에 잘 생각해보면, 두 번째 셤 등수가 나보다 낮은 녀석 들 중에 세 번째 셤 점수의 최소 값을 안다면, 내가 굉장한 그룹에 낄 수 있는지 없는 지 알기 쉽게 된다.

 

 이게 풀이이고, 맨 첨에 나는 팬윅 트리로 하려다가, 팬윅 트리는 제한적인 상황에서만 쓰니깐 세그먼트 연습할 겸 세그먼트로 하기로 했다. 사실 세그먼트 인덱싱이 좀 미숙한 감이 있어서 그래서 연습하기로 했다. 근데 아주 크은 실 수를 했다.

int add(int node, int idx, int value, int start, int end) {
	if (start == end) { return tree[node] = value; }
	if (idx < start || end < idx)return tree[node];
	int mid = (start + end) / 2;
	return tree[node] = min(
		add(node * 2, idx, value, start, mid),
		add(node * 2 + 1, idx, value, mid + 1, end));
}

 세그먼트 트리 update 함수인데 위와 같이 해버렸다 TT.. 이거 땜에 나 오늘 밖에 나가서 달리기 할라 했는데 시간만 늦어졌다. 젠장,,, 당장 나가 뛰고 싶은데,, 너무 늦었어,,, 짱나서 블로그에 올린다. ㅜ

 암튼 무엇이 문제였냐면 start==end를 하고 idx가 구간에 있느냐 거르기를 했다. 당연히 start end가 2, 3 이고 idx가 3이었다면 mid가 2가 되어 add 함수를 재귀적으로 부른다. 이때 첫 번째 add에서 start, end 가 2가 되면서 idx가 3인 곳에 값을 새겨야 하는데 idx가 2인 곳에도 새겨버려 한 번에 두 개씩 값이 새겨진다.

 애초에 mid해서 재귀적으로 add 부를 때 범위를 체크 해야 했는데, 심지어 해야 하나 생각도 했는데 에이 설마 하면서 넘어간게 내 2시간을 날릴 줄이야.... 후

 다음부터 그러지 말자.. 내일 아침에 달리기 하고 밥먹고 점심 전에 헬스 가야 겠다. 하기로 마음 먹은 건 해야지.... 

 전체 코드를 보고 싶다면 아래 붙여 놓겠다.

 

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

using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> iP;
const int INF = 987654321;
const int MAXN = 2000001;
int tree[MAXN];

int query(int start, int end, int node, int left, int right) {
	if (left > end || right < start)return INF;
	if (left <= start && end <= right)return tree[node];
	int mid = (start + end) / 2;
	return min(query(start, mid, node * 2, left, right), query(mid + 1, end, node * 2 + 1, left, right));
}

int add(int node, int idx, int value, int start, int end) {
	if (idx < start || end < idx)return tree[node];
	if (start == end) { return tree[node] = value; }
	int mid = (start + end) / 2;
	return tree[node] = min(
		add(node * 2, idx, value, start, mid),
		add(node * 2 + 1, idx, value, mid + 1, end));
}
int a[500001];
int main() {

	ios_base::sync_with_stdio();
	cin.tie(NULL);
	cout.tie(NULL);
	fill(&tree[0], &tree[MAXN], INF);
	
	int N;
	cin >> N;
	vector<iP> nums(N);

	for (int i = 0; i < N; i++) {
		cin >> a[i];
		nums[a[i] - 1].first = i + 1;
	}
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		nums[a[i] - 1].second.first = i + 1;
	}
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		nums[a[i] - 1].second.second = i + 1;
	}
	sort(nums.begin(), nums.end());

	int ret = 1;
	add(1, nums[0].second.first, nums[0].second.second, 1, N);
	for (int i = 1; i < N; i++) {
		if (query(1, N, 1, 1, nums[i].second.first) > nums[i].second.second)
			ret++;
		add(1, nums[i].second.first, nums[i].second.second, 1, N);
	}
	cout << ret << endl;
	return 0;
}