백준 12846 c++ "무서운 아르바이트" -PlusUltraCode-

https://www.acmicpc.net/pr

[필자 사고]

필자는 스택을 이용하여 해당 문제를 해결했다.

과거에 풀어 봤던 히스토그램 문제와 많이 비슷해서 손쉽게 해결할 수 있었다.

문제를 풀면서 조심해야 될 점은 스택의 값이 idx가 들어가야 된다는 점.

그리고 가로 길이를 잘 계산해야 된다. 필자는 현재 i 에서 스택의 stack.top()를 뺀뒤 -1을 하여
최대값을 계산할 수 있게 코드를 작성했다.

 

마지막으로 스택에 남아있는 값ㅇ 있을수 있으므로 마무리 점검 또한 했다.

[코드 해설]

 

• 입력 처리 (Input 함수)
  • 배열 arr에 N개의 숫자를 입력받아 저장합니다.
  • N은 배열의 크기(또는 막대기의 개수)를 나타냅니다.
• 게임 시작 (Game_Start 함수)
  • 스택을 사용하여 현재 높이보다 낮아지는 구간을 만날 때까지의 최대 직사각형 넓이를 계산합니다.
  • 코드는 두 부분으로 구성됩니다:
    • 첫 번째 루프: 배열을 순회하며 스택 처리
      • 배열의 각 원소 arr[i]를 순회합니다.
      • 현재 값 arr[i]가 스택의 최상단 원소(arr[myStack.top()])보다 작을 경우, 스택의 최상단 값(막대)을 기준으로 최대 넓이를 계산합니다.
        • 스택에서 꺼낸 막대의 높이를 기준으로 너비를 계산:
          • 스택이 비어 있으면 현재 인덱스 i까지의 너비.
          • 스택에 다른 값이 남아 있으면, 이전 막대와의 거리로 너비를 계산.
      • 계산된 넓이를 resultMax와 비교하여 최대값을 갱신.
      • 이후, 현재 인덱스를 스택에 삽입.
    • 두 번째 루프: 스택에 남아 있는 원소 처리
      • 배열의 끝까지 순회한 후, 스택에 남아 있는 원소들을 처리합니다.
      • 스택의 각 원소에 대해 최대 넓이를 계산:
        • 스택이 비어 있으면 전체 배열의 너비를 사용.
        • 스택에 다른 값이 남아 있으면 마지막 막대와의 거리로 너비를 계산.
      • 계산된 넓이를 resultMax와 비교하여 최대값을 갱신.
• 결과 출력
  • 최종적으로 계산된 최대 넓이 resultMax를 출력합니다.
• main 함수
  • Input 함수로 입력을 처리한 후, Game_Start 함수를 호출하여 계산을 수행합니다.
  • ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)는 입출력 성능을 최적화하기 위해 사용됩니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<long> arr;
int N;
stack<long> myStack;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		long num;
		cin >> num;
		arr.push_back(num);
	}
}

void Game_Start() {
	
	long resultMax = -1;
	for (int i = 0; i < N; i++ ) {
		
		while (!myStack.empty() && arr[i] < arr[myStack.top()]) {
			int topIdx = myStack.top();
			myStack.pop();
			

			int currentIdx = 0;
			if (myStack.empty()) {
				currentIdx = i;
			}
			else {
				currentIdx = i - myStack.top()-1;
			}

			resultMax = max(resultMax, arr[topIdx] * currentIdx);

		}

		myStack.push(i);
	}

	while (!myStack.empty()) {
		int topIdx = myStack.top();
		myStack.pop();


		int currentIdx = 0;
		if (myStack.empty()) {
			currentIdx = N;
		}
		else {
			currentIdx = N - myStack.top() - 1;
		}

		resultMax = max(resultMax, arr[topIdx] * currentIdx);
	}

	cout << resultMax;
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	Input();
	Game_Start();
}