백준 2304 - 창고 다각형

백준 2304 - 창고 다각형

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

"두번 틀림"

★ 풀이

생각하기 쉽지 않았던 문제.. 먼저 그림을 통해 풀이 방식을 설명하자면

기본 구상은 이렇게 이루어 진다.

가장 먼저 해야할 일은 list를 l기준으로 오름차순 정렬을 해주어야 하고, 그 다음부터

1. 오른쪽으로 탐색을 실행한다. 자신보다 큰 기둥이 나오면 거기까지의 넓이를 계산해서 더해준다.

2. 왼쪽으로 탐색을 실행한다. 자신보다 큰 기둥이 나오면 거기까지의 넓이를 계산해서 더해준다.

이렇게만 하면 이 빨간색 부분이 빠지게 된다. 그렇기 때문에 마지막에

3. max 값에 해당하는 기둥의 넓이를 따로 또 더해준다.

틀렸던 이유는 처음엔 이 max값을 고려하지 않아서 틀렸고, 두번째에는 오른쪽 탐색과 왼쪽 탐색 모두 같은 영역을 포함하는 경우(예를 들어 모든 기둥이 같은 높이를 지니는 경우)를 고려하지 않아서 틀렸다. 두 번째 같은 경우엔 오른쪽 탐색을 끝낸 이후 왼쪽 탐색을 실행하지 않아야 하는데, 이를 위해서 오른쪽 탐색시에 max값을 지속적으로 갱신하면서 그 기둥이 위치하는 index를 기록하고 왼쪽 탐색시에는 index왼쪽 부분은 탐색하지 않도록 설정하면 더 이상 중복값을 갖는 경우가 사라지게 되어 문제점을 해결할 수 있다.

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { int n = Integer.parseInt(br.readLine()); ArrayList list = new ArrayList<>(); for(int k = 0; k=x; i--) { Pair cur = list.get(i); if(prev.h <= cur.h) { ans+=(prev.l - cur.l)*prev.h; prev = cur; } } System.out.println(ans+max); } } class Pair implements Comparable{ int l,h; Pair(int l, int h){ this.l = l; this.h = h; } public int compareTo(Pair o) { return this.l - o.l; } }

from http://sweet-smell.tistory.com/125 by ccl(A) rewrite - 2021-12-02 02:27:52