[백준 - 1276] 골드5 - 교각 놓기

www.acmicpc.net/problem/1276

1276번: 교각 놓기

 

1. 유형

그리디, 정렬

 

2. 풀이

• 입력값 전처리
• 높이가 낮은 순으로 우선순위 정렬
• 메모리제이션

 

전처리 과정

문제를 풀기 위해서 입력값을 한번 전처리 과정을 거쳐야 합니다.

1 5 10 값이 들어오면 배열의 index로는 5 ~ 9 까지만 차지합니다

3 1 5 값이 들어오면 index로는 1 ~ 4 까지만 들어옵니다.

즉, 입력값을 배열로 전처리 하고 싶으면 끝값(10, 5 등..)을 -1만큼 줄여줘야 합니다.

 

우선순위 정렬

위의 그림은 교각이 교각위에 쌓이는 구조 입니다. 따라서 높이가 가장 낮은 교각부터 길이를 구해야 합니다.

따라서, 높이가 낮은 순으로 정렬해줍니다.

 

그 후, 교각 높이를 메모리제이션 해서 높이를 갱신해주는 식으로 구현하면 됩니다.

 

 

3. 코드

package 그리디;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Back_1276교각놓기 {
	static class Pair implements Comparable<Pair> {
		int y, x, x2;

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

		@Override
		public int compareTo(Pair o) {
			return this.y - o.y;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int n = Integer.valueOf(st.nextToken());
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int y = Integer.valueOf(st.nextToken());
			int x1 = Integer.valueOf(st.nextToken());
			int x2 = Integer.valueOf(st.nextToken());
			pq.add(new Pair(y, x1, x2));
		}
		int ans = 0;
		int maxList[] = new int[10001];
		// q가 빌때까지 반복
		while (!pq.isEmpty()) {
			Pair cur = pq.poll();
			// x1에서 x2까지 탐색
			ans += cur.y - maxList[cur.x];
			ans += cur.y - maxList[cur.x2-1];
			for (int i = cur.x; i < cur.x2; i++) {
				// maxList 보다 y가 더 크다면 차만큼 더하고 minList업데이트
				maxList[i] = cur.y;
			}
		}
		System.out.println(ans);
	}
}

 

우선순위 정렬

	static class Pair implements Comparable<Pair> {
		int y, x, x2;

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

		@Override
		public int compareTo(Pair o) {
			return this.y - o.y;
		}
	}

 

현재와 최대값의 차이만큼 더하기

	ans += cur.y - maxList[cur.x];
	ans += cur.y - maxList[cur.x2-1];