[S3] 백준 17952번 과제는 끝나지 않아! C++ 스택

리뷰

 

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

스택을 활용해 과제의 최고점을 구하는 문제

 

 

전역 변수

• n : 이번 학기가 몇 분인지를 저장할 변수
• stack : 스택으로 사용할 pair<int, int>타입 벡터

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, 변수 sun을 0으로 초기화한다.
2. n번의 for문을 개행하고, 매 루프마다 변수 op를 초기화 하고, 값을 입력 받는다.
3. 만약 op가 1이라면 변수 a, t를 초기화 하고, 값을 입력 받는다.
4. 만약 t가 1이라면 sum에 a를 더해준다, 아니라면 stack에 {a, --t}를 push한다.
5. op가 0이라면 stack이 비지 않았고, stack의 back의 second를 전위감소 시켜준다.
6. 감소 후 stack의 back의 second가 0일 경우 sum에 stack의 back의 first를 더해주고, stack에서 마지막 요소를 pop한다.
7. sum에 저장된 값을 출력한다.

 

트러블 슈팅

1. 스택에 아무것도 존재하지 않을 때에도 stack의 back을 참고하려고 하여 WA를 받았다.
2. stack의 back을 참조하기 전에 stack이 empty상태인지를 확인하는 로직을 추가하여 AC를 받았다.

 

참고 사항

1. N이 최대 100만이고, A가 최대 100이므로 int 범위 내로 처리할 수 있다.
2. 입력 값이 많으므로 빠른 입출력을 권장한다.

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;
using pii = pair<int, int>;

int n;
vector<pii> stack;

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

	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		int op; cin >> op;

		if (op == 1) {
			int a, t; cin >> a >> t;

			if (t == 1) sum += a;
			else stack.push_back({ a, --t });
		}
		else {
			if (!stack.empty() && !--stack.back().second) {
				sum += stack.back().first;
				stack.pop_back();
			}
		}
	}
	cout << sum;
}