글 읽기 - 반례를 아무리 생각해도 찾을 수가 없습니다..

alalssg 5년 전 0

기존에 다른곳에서 풀었던 문제라 쉽게 풀릴줄 알고 시도를 했습니다만 아무리 시도를 해도 틀렸다고 나오는데

제가 어느 곳을 빼놓고 있는지 잘 모르겠습니다.

이문제를 풀면서 먼저 좌우에는 높이를 0으로 두고 문제를 접근하는것이 좋다고 해서 배열의 크기를 입력받은 수보다 + 2 하여 0번 인덱스와 size+1 번인덱스는 0이 들어간 상태에서 시작합니다.

스택에 0번인덱스를 삽입하고

반복문으로 1번 인덱스에서 배열의 끝까지 돌면서 현재 인덱스 i보다 스택 top에 있는 막대기의 높이가 크다면 pop을해서 높이와 너비를 구한뒤 결과를 구했습니다.

하지만 제가 어느 부분을 놓친건지 자세히 알 수가 없어 도움을 요청드리고자 합니다..

제가 어디서 놓치고 있는게 있는걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(br.readLine());
		int[] arr = new int[size+2];

		for(int i=1; i <= size; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Stack<Integer> stack = new Stack<Integer>();
		int result = size;
		
		stack.push(0);
		for(int i=1; i <= size+1; i++) {
			while(!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
				int height = arr[stack.peek()];
				stack.pop();
				int width = i - stack.peek() - 1;
				
				result = Math.max(result, width*height);
			}
			stack.push(i);
		}
		System.out.println(result);
	}
}

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

문제

문제

출처

ICPC

반례를 아무리 생각해도 찾을 수가 없습니다..

alalssg 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말