[백준] 20207 달력

20207번: 달력 (acmicpc.net)

20207번: 달력

 

 

문제

 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 

여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.

• 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
• 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다. 
• 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.

달력은 다음과 같은 규칙을 따른다.

• 일정은 시작날짜와 종료날짜를 포함한다.
• 시작일이 가장 앞선 일정부터 차례대로 채워진다.
• 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
• 일정은 가능한 최 상단에 배치된다.
• 일정 하나의 세로의 길이는 1이다. 
• 하루의 폭은 1이다. 

위의 그림에서와 같이 일정이 주어졌다고 하자. 여기서 코팅지의 면적은 아래의 파란색 영역과 같다.

이때 코팅지의 크기의 합은 3 x 8 + 2 x 2 = 28이다. 

일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자.

 

 

내풀이

처음에는 최근에 풀은 백준 11000 강의실 문제가 생각이 나서 비슷하게 우선순위 큐 2개를 이용하여 해결해보려고 시도했고 뭔가 2프로 부족한 느낌이라 캘린더를 진짜 채우는 방식으로 바꾸어서 해결했다.

 

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

public class Main{
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src="5\n" +
			"1 9\n" +
			"8 9\n" +
			"4 6\n" +
			"3 4\n" +
			"2 5";

	static int N,result;
	static boolean[][] calendar;

	public static void main(String arg[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input= new BufferedReader(new StringReader(src));

		N = Integer.parseInt(input.readLine());
		StringTokenizer str;

		int maxday = 0;
		PriorityQueue<Schedule> PQ = new PriorityQueue();
		for (int i = 0; i < N; i++) {
			str = new StringTokenizer(input.readLine());
			int start = Integer.parseInt(str.nextToken());
			int end = Integer.parseInt(str.nextToken());
			PQ.add(new Schedule(start, end));
			maxday = Math.max(maxday, end); //마지막날 구한다
		}

		calendar = new boolean[N][maxday + 2];

		result = 0;

		//일정 다 꺼내면서
		while (!PQ.isEmpty()) {
			Schedule schedule = PQ.poll();

			for (int i = 0; i < N; i++) {
				//이미 배치했다면
				if (calendar[i][schedule.start]) {
					continue;
				}
				//일정 배치
				for (int j = schedule.start; j <= schedule.end; j++) {
					calendar[i][j] = true;
				}
				break;
			}

		}

		/*for (int i = 0; i < N; i++) {
			for (int j = 0; j < maxday+2; j++) {
				System.out.print(calendar[i][j]+" ");
			}
			System.out.println();
		}*/

		int wideStart = 365;
		int wideEnd = 0;
		int height= 0;

		//이 과정을 통해 블럭의 좌우 끝과 높이 구함
		for(int j =1; j<calendar[0].length;j++){
			boolean stop = true;
			for (int i = 0; i < N; i++) {
				if (calendar[i][j]) {
					wideEnd = Math.max(wideEnd, j); //마지막 수업 끝
					wideStart = Math.min(wideStart, j); //첫 수업 시작
					height = Math.max(height, i + 1); //겹치는 수업 나타냄
					stop = false;
				}
			}
			//위에서 for문으로 세로로 탐색했는데 stop이 false가 안됬다는 것은
			//이 시간대에 일정이 없었다는 것이고 즉 블럭이 형성된다는 것을 의미
			//블럭 만들어지면 블럭 계산하고 초기화
			if (stop) {
				//System.out.println(wideEnd+" "+wideStart+" "+height);
				result += ((wideEnd - wideStart + 1) * height);
				wideStart = 365;
				wideEnd = 0;
				height = 0;
			}
		}

		System.out.println(result);
	}

	static class Schedule implements Comparable<Schedule> {
		public int start;
		public int end;

		public Schedule(int start, int end) {
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Schedule o) {
			if (this.start == o.start) {
				return o.end - this.end;
			} else {
				return this.start - o.start;
			}
		}
	}
}