글 읽기 - 제가 이해하지 못한 규칙이 있을까요?

shkk0628 2년 전 0

알고리즘 원리는

매 반복마다

새로운 키를 입력 받습니다.

스택 안에 있는 녀석들은 새로운 키와 쌍을 이룰 수 있는 녀석들입니다.

그래서 새로운 키로 인해 생기는 쌍의 수는 S.size()만큼 늘어납니다.

그 후 새로운 키로 인해서 가려지는 녀석들을 스택에서 제외합니다.

그러면 다음에 새로운 키가 들어오면 스택 안의 녀석들과는 쌍을 이룰 수 있습니다.

그 다음 새로운 키를 스택에 넣습니다.

#include <bits/stdc++.h>
using namespace std;

int N;
long long height, cnt;
stack<int> S;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		cin >> height;
		cnt += S.size();
		while (!S.empty() && S.top() < height) S.pop();
		S.push(height);
	}
	cout << cnt;
}

shkk0628 2년 전 0

3 2 1이 안되는 경우군요 해결해보고 오겠습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 이해하지 못한 규칙이 있을까요?

shkk0628 2년 전 0

shkk0628 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말