boj, 백준) 2336. 굉장한 학생( C++)

1. 문제 링크

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

2336번: 굉장한 학생

 

2. 문제 개요

어떤 학생 x보다 시험 3개의 성적이 높은 학생 y가 있다면, 학생 y는 x보다 대단하다고 한다.

어떤 학생 y보다 대단한 학생이 없으면 학생 y는 굉장하다고 한다.

 

굉장한 학생의 수를 구하는 프로그램을 작성하시오.

 

3. 문제 풀이

문제 힌트 없이 바로 풀이로 넘어가겠다.

이 부분은 다른 블로그에도 풀이가 많다. 하지만 모두 똑같이 생각하듯이, 글로 설명되어있어서 이해가 잘 안 될 거라고 생각한다.

 

일단 글로 한번 설명하고, 정리를 통해서 완벽하게 이해하도록 해보자.

첫 번째 성적을 기준으로 오름차순으로 정렬해보자. 이게 무슨 의미 일까?

첫 번째 성적을 1, 2, 3, 4, 5,... 10으로 정렬해보자. 그러면 다음과 같이 정렬될 것이다.

 

정렬결과

원래라면 학생 번호가 1~10으로 정렬되어 있을 것이다. 그런데 이렇게 첫 번째 점수를 기준으로 정렬할 경우 얻게되는 정보와 잃는 정보가 있다.

 

얻는 정보로는 첫 번째 점수를 기준으로 순회할때, 예를들어 첫번째 학생의 경우 무조건 굉장하다. 왜냐하면 첫번째 점수가 1등임을 보장하기 때문에 누군가가 첫번째 학생보다 대단하지 않다는 것을 의미한다.

 

이제 두 번째 학생을 볼때, 첫번째 학생이 두번째 학생보다 대단한지만 체크하면 된다. 

이대로 가보면 i번째 학생은 1~i-1번째 학생이 나보다 대단한지만 체크하면 됨을 보장한다는 것이다.

 

그럼 찾아보아야 할 정보는 두 번째 점수, 세 번째 점수이다.

어떻게 이 점수를 logn으로 한 번만에 찾을 수 있을까?

 

바로 두 번째 등수의 인덱스에 세 번째 등수의 값을 넣어주면 세그먼트 트리 1개에 모든 정보를 나타낼 수 있다.

1~두 번째 등수의 범위에 최솟값을 찾는 쿼리를 날리고, 반환 값이 이번에 비교할 학생의 등수보다 높다면 굉장하다.

 

뭐 다른 블로그에도 있듯이, 정렬해서 세그먼트트리를 만들어서 최솟값을 만드는건 알겠는데, 이게 어떤걸 의미하는 건가? 라는 궁금증이 생길 수도 있다.

★★정리해보면,

조건 : 굉장한 학생 -> 나 보다 3번 다 우수한 학생이 없어야 함.

① 세그먼트 트리에 존재 ( 나보다 1번 시험이 우수한 학생 )

② 세그먼트 트리의 [1, 두 번째 등수]index에 존재 ( 나보다 1, 2번 시험이 우수한 학생 )

③ [1, 두번째 등수]의 구간의 최솟값이 나보다 작음 ( 작다는 것은 낮은 등수, 즉 나보다 3번째 시험이 우수한 학생이 적어도 '존재')

결론 : 1,2,3을 다 만족하면 나보다 대단한 학생이 존재.라는 의미이다. => 나는 굉장하지 않다는 것을 의미

 

그래서 i 번째 학생을 비교할 때 최솟값을 찾아본 뒤, i번째 학생을 세그먼트 트리에 삽입하자.

 

 

 

4. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int INF = 987654321;

struct student
{
	int first, second, third;

	bool operator < (const student &b)
	{
		return first < b.first;
	}
};

int n;
vector<student> v;

class Segment_Tree {
	public:
		Segment_Tree(int tree_size) { tree.resize(tree_size, INF); }

		int query_min(int cur, int start, int end, int left, int right)
		{
			if (end < left || right < start)
				return INF;
			if (left <= start && end <= right)
				return tree[cur];

			int mid = (start + end) / 2;

			return min(query_min(cur * 2, start, mid, left, right), query_min(cur * 2 + 1, mid + 1, end, left, right));
		}

		int query_update(int cur, int start, int end, int target, int val)
		{
			if (target < start || end < target)
				return tree[cur];

			if (start == end)
				return tree[cur] = val;
			
			int mid = (start + end) / 2;
			return tree[cur] = min(query_update(cur * 2, start, mid, target, val), query_update(cur * 2 + 1, mid + 1, end, target, val));
		}

		vector<int> tree;
};

int main()
{
	scanf("%d", &n);
	v.resize(n + 1);

	for (int i = 1; i <= n; ++i) {
		int s;
		scanf("%d", &s);
		v[s].first = i;
	}
	for (int i = 1; i <= n; ++i) {
		int s;
		scanf("%d", &s);
		v[s].second = i;
	}
	for (int i = 1; i <= n; ++i) {
		int s;
		scanf("%d", &s);
		v[s].third = i;
	}

	sort(++v.begin(), v.end());
	
	int h = (int)ceil(log2(n));
	int tree_size = 1 << (h + 1);
	Segment_Tree sgt(tree_size);
	int ans = 0;

	for (int i = 1; i <= n; ++i)
	{
		int ret = sgt.query_min(1, 1, n, 1, v[i].second);
		if (ret > v[i].third)
			++ans;
		sgt.query_update(1, 1, n, v[i].second, v[i].third);
	}

	printf("%d", ans);

	return 0;
}

 

5. 결과

지적 댓글 환영입니다 :)