[백준/C++] 오아시스 재결합

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 두 사람이 서로 볼 수 있는지 수를 계산하는 문제다.

 

A와 B를 선택해 그 사이에 사람의 키를 비교하기에는 매우 비 효율적이다.

 

두 사람 사이에 키가 큰 사람이 없기만 하면 서로 마주볼 수 있으므로 이를 이용해 문제를 풀면 된다.

 

그럼 여기서 두 사람 사이에 키가 큰 사람이 없다는 것은 어떤 의미일까?

 

잘 생각해보면 A와 B의 사이가 아닌 곳에는 키가 큰 사람이 있어도 된다는 뜻이다.

 

아래 그림을 한번 보면

 

A와 B 사이에 키가 큰 사람이 없으므로 A와 B는 볼 수 있다.

 

이를 이용하면 A의 왼쪽에는 키가 큰 사람이 와도 전혀 영향이 없다는 사실을 알 수 있다.

 

이제 문제를 푸는 방법은 다음과 같다.

 

사람을 순서대로 추가하는데, 왼쪽보다 키가 큰 사람이 오면 더 이상 왼쪽에 있는 사람은 오른쪽에 있는 사람을 볼 수 없다.

 

예를 들어 i번째 사람이 왼쪽에 있는 n번째 사람보다 키가 크다면, n번째 사람은 i번째 사람 이후에 오는 사람을 볼 수 없는 것이다.

n번째 사람과 i+a번째인 사람사이에 n번째 사람보다 키가 큰 i번째 사람이 존재하기 때문이다.

 

그러므로 이 경우 마주볼 수 있는 사람의 수를 +1 하고 n번째 사람을 제거한다.

(조건에 의해 n번째 사람과 i번째 사람은 서로 볼 수 있다.)

 

아후 n번째 사람의 왼쪽에 있으면서 키가 큰 사람을 찾는다.

(m번째 사람이라고 하자)

 

마찬가지로  m번째 사람도 i번째 사람과 키를 비교하는 과정을 반복하면 된다.

 

이때, m번째 사람이 i번째 사람보다 키가 크다면, 마주볼 수 있는 사람의 수를 +1하면 끝이다.

 

이렇게 키가 큰 사람부터 작은 사람 순서로 저장을 하면, 서로 마주볼 수 있는 사람인지를 빠르게 판단할 수 있게 된다.

 

여기서 아래와 같이 키가 같은 사람이 나오는 경우가 있는데 키가 같은 사람 뒤에 오는 사람은 키가 같은 사람들을 전부 볼 수 있으므로 키가 같은 사람의 수 만큼 추가해주어야 한다.

 

이 문제를 이러한 방식으로 풀 때, 가장 최근에 키가 기록된 사람과 비교를 하고 제거하는 방식으로 문제를 푼다.

 

그러므로 stack 자료구조를 이용하면 더 쉽게 문제를 해결할 수 있다.

 

 

​

[아이디어 정리]

1. 키와 같은 키를 가진 사람이 몇 명인지를 저장할 stack을 만든다. 
2. stack의 맨 위의 사람과 키를 비교하고 stack의 사람이 키가 더 크다면, 맨 위의 사람과 키가 같은 사람의 수만큼 answer에 더한다.
3. 만약 stack의 맨 위의 사람의 키가 더 작다면, 맨 위의 사람과 키가 같은 사람의 수 만큼 answer에 더하고 stack의 맨위의 사람을 제거한다. (stack의 사람이 키가 더 클 때 까지 반복, 만약 비어있다면 종료하고 현재 사람을 추가한다)
4. 만약 stack의 맨 위의 사람과 키가 같다면, stack의 맨 위의 사람과 키가 같은 사람의 수 만큼 answer에 더하고 키가 같은 사람의 수를 +1 더한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;
	stack<pair<int, int>> st;
	pair<int, int> np;
	int a;
	long long answer = 0;
	for (int i = 0; i < N; i++) 
	{
		cin >> a;
		while (true) 
		{
			if (!st.empty() && st.top().first<a)
			{
				answer += st.top().second;
				st.pop();
			}
			else if (!st.empty() && st.top().first == a)
			{
				np = st.top();
				st.pop();
				if (!st.empty()) //앞에 키가 같지 않은 큰 사람이 있다면
				{
					answer += 1;
				}
				answer += np.second;
				np.second += 1;
				st.push(np);
				break;
			}
			else 
			{
				if (!st.empty()) 
				{
					answer += 1;
				}
				st.push(make_pair(a, 1));
				break;
			}
		}
	}
	cout << answer;
	return 0;
}

 

---

기준을 잘 잡으면 쉽게 해결할 수 있는 문제였다

 

 

3015번: 오아시스 재결합