백준_2304 창고 다각형(자바) / 브루드 포스 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Back_2304 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<top> arr = new ArrayList<>();
		int ans=0;

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr.add(new top(x, y));
		}
		Collections.sort(arr);
		
		int maxX=0;

		//오른쪽에서 왼쪽으로
		top currenttop=arr.get(0);
		for (int i = 1; i < N; i++) {
			if(currenttop.y <= arr.get(i).y) {
				ans += (arr.get(i).x - currenttop.x) * currenttop.y;
				currenttop = arr.get(i);
				maxX = i;
			}
		}
		
		//왼쪽에서 오른쪽으로
		currenttop = arr.get(N-1);
		for (int i = 0; i < N-maxX; i++) {
			if(currenttop.y <= arr.get(N-i-1).y) {
				ans += (currenttop.x - arr.get(N-i-1).x ) * currenttop.y;
				currenttop = arr.get(N-i-1);
			}
		}
		ans += currenttop.y;
		System.out.println(ans);
	}
	
	static class top implements Comparable<top> {
		int x;
		int y;

		public top(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(top o) {
			// TODO Auto-generated method stub
			return this.x - o.x;
		}

	}
}

- 이 문제는 브루드 포스 알고리즘 문제입니다.

- 그리디 구현하듯이 Comparable를 써서 위치를 오름차순이 되게 정렬을 했습니다.

- 앞에서 부터 진행을 하고, 또한 뒤에서 진행을 이어서 해줍니다.

- for 문 안에서 높이가 같은 경우도 체크를 해줘야 합니다.

- 위 사진과 같이 만약에 높이가 가장 높은 부분이 여러개 인 경우를 생각해 봤을 때,

같은 경우도 체크를 해줘야 합니다.