방과후
ALGORITHM NOTE약 2분

BOJ 4055 - 파티가 좋아 파티가 좋아

30분만 찍고 나와도 예의는 지키는 걸로

#algorithm#boj#gold#greedy#sorting
아카이브로 돌아가기

문제 링크

문제

아람이는 고등학교를 졸업하였다. 아람이네 마을에서는 학교의 모든 졸업생들이 참가할 수 있는 다양한 파티가 관습처럼 열리고 있다. 파티를 좋아하는 아람이는 최대한 많은 파티에 참가하려고 한다.

평일에 열리는 파티는 저녁에만 두세개가 열리지만 토요일에는 하루종일 많은 파티들이 열린다. 어떤 파티는 아침 8시에 시작하여 자정(24시)에 끝나기도 한다. 아람이는 최대한 많은 파티에 참가하고 싶다.

각각의 파티는 시작시간과 끝시간이 정해져있다. 파티는 정각에 시작하여 정각에 끝난다. 예를 들어 10시에 파티가 시작한 파티가 오후2시(14시)에 끝날 수도 있고 가장 일찍 시작하는 파티는 아침 8시에 시작하고 이웃들의 항의가 있을 수 있기 때문에 아무리 늦게 끝나도 24시에는 끝나게 된다. 파티에 있을 때는 최소한 30분은 있어야 예의에 어긋나지 않는다. 아람이는 예의를 지키는 사람이다. 아람이는 축지법을 쓰기 때문에 파티간 이동시간은 신경쓰지 않아도 된다. 더 이상 참가할 파티가 없으면 아람이는 집에 돌아간다.

아람이가 갈 수 있는 최대 파티 수는 몇 개인지 찾는 프로그램을 작성하시오.

입력

여러 개의 테스트케이스가 주어진다. 각 테스트케이스의 첫 번째 줄에 정수 p가 주어진다. (p <= 100) 이 p는 그 날에 열리는 파티의 수이다. p가 0이면 입력의 끝을 의미한다. 이어지는 p개의 줄에는 s와 e가 주어진다. (8 <= s <= e <= 24) s는 파티의 시작 시간, e는 파티의 끝나는 시간을 의미한다. 시작 시간과 끝 시간이 같은 파티가 주어질 수도 있다.

n은 최대 갈 수 있는 파티의 수이고 d는 몇 번째 테스트 케이스인지를 가리킨다. 테스트케이스는 1부터 시작한다.

풀이

한 파티에 30분만 있어도 되므로, 시간을 30분 단위의 슬롯으로 나눠 생각하면 된다. 하루 전체는 8시부터 24시까지이므로 총 32개의 반시간 구간만 관리하면 충분하다.

코드에서는 파티를 종료 시간이 빠른 순으로 정렬한 뒤, 각 파티가 열리는 구간 안에서 아직 사용하지 않은 가장 이른 30분 슬롯 하나를 배정한다. 슬롯 하나만 배정되면 그 파티는 참석 가능하다고 볼 수 있다.

이 방식은 종료가 빠른 파티부터 먼저 처리하는 전형적인 그리디다. 늦게 끝나는 파티를 먼저 잡아버리면, 짧은 구간 파티들이 들어갈 자리가 사라질 수 있기 때문이다.

문제를 이렇게 바꾸면 "각 구간 안에서 슬롯 하나씩만 차지하는 최대 개수 선택"이 된다. 슬롯 수가 32개로 작아서, 복잡한 자료구조 없이도 각 파티의 가능한 시간 구간을 직접 확인하면서 배정할 수 있다.

결국 핵심은 긴 시간 참석이 아니라 "가능한 반시간 하나를 어디에 꽂을 것인가"다. 관점을 반시간 슬롯 배정 문제로 바꾸면 구현이 훨씬 단순해진다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
	
	static class Party implements Comparable<Party> {
		int start, end;
		public Party (int start, int end) {
			this.start = start;
			this.end = end;
		}
		
		@Override
		public int compareTo(Party o) {
			if (this.end == o.end) return this.start - o.start;
			return this.end - o.end;
		}
	}
		
	static ArrayList<Party> parties;
	static String message = "On day %d Emma can attend as many as %d parties.\n";
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int cnt = 0;
		
		while (true) {
			int N = Integer.parseInt(br.readLine());
			
			if (N == 0) break;
		
			cnt++;
			parties = new ArrayList<>();
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				parties.add(new Party(start, end));
			}
			
			Collections.sort(parties);
			
			int ans = solve(N);
			sb.append(String.format(message, cnt, ans));
		}
				
		System.out.println(sb);
	}
	
	
//	static int solve(int N) {
//		int ans = 0;
//		for (int i = 8; i < 24; i++) {
//			for (int j = 0; j < 2; j++) {
//				for (int k = 0; k < parties.size(); k++) {
//					Party p = parties.get(k);
//					if (i >= p.start && i < p.end) {
//						ans++;
//						parties.remove(k);
//						break;
//					}
//				}
//				
//			}
//		}
//		
//		return ans;
//	}
	
	static int solve(int N) {
		int ans = 0;
		// 30분 단위로 기록
		boolean[] time = new boolean[32];
		
		for (Party p : parties) {
			int start = (p.start - 8) * 2;
			int end = (p.end - 8) * 2;
			
			for (int i = start; i < end; i++) {
				if (!time[i]) {
					time[i] = true;
					ans++;
					break;
				}
			}
		}
		
		return ans;
	}
 
}

복잡도

  • 시간 복잡도: O(plog⁡p+32p)O(p \log p + 32p)
  • 공간 복잡도: O(p)O(p)

마무리

시간 전체가 길어 보여도 30분 단위로 쪼개면 상태 수는 아주 작다. 종료 시간이 빠른 파티부터 슬롯 하나씩 배정하는 그리디가 잘 맞는 문제다.