Baekjoon - 1931

문제

Solved.ac class3

1차시도

public class Main {
	private static boolean[] isAcceptable;
	private static ArrayList<TimeTable> meetings;
	private static int size;
	private static int max = -1;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		size = Integer.parseInt(br.readLine());
		meetings = new ArrayList<>();
		isAcceptable = new boolean[size];

		for (int i = 0; i < size; i++) {
			meetings.add(new TimeTable(br.readLine()));
		}
		meetings.sort(new Comparator<TimeTable>() {
			@Override
			public int compare(TimeTable o1, TimeTable o2) {
				if (o1.start == o2.start) {
					return o1.end - o2.end;
				}
				return o1.start - o2.start;
			}
		});

		solve(0, 0, 0);
		System.out.println(max);

	}

	private static void solve(int visit, int lastTime, int totalValue) {
		if (totalValue > max) {
			max = totalValue;
		}
		isAcceptable[visit] = true;
		for (int i = visit + 1; i < size; i++) {
			TimeTable willVisit = meetings.get(i);
			if (willVisit.start >= lastTime) {
				solve(i, willVisit.end, totalValue + 1);
			}
		}
		isAcceptable[visit] = false;
	}


	private static class TimeTable {
		private final int start;
		private final int end;

		public TimeTable(String times) {
			String[] split = times.split(" ");
			this.start = Integer.parseInt(split[0]);
			this.end = Integer.parseInt(split[1]);
		}
	}

}

시간초과

2차시도

고민하다가 찾아봤다
위와 같은 문제를 ActivitySelectionProblem이라고 한다.

가장 간단한 방법은
1. 종료시간 순으로 정렬한 뒤
2. 가장 짧은거 선택 후 겹치는거 제외, 나머지 선택을 반복한다.

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int size = Integer.parseInt(br.readLine());
		ArrayList<TimeTable> meetings = new ArrayList<>();
		int count = 0;
		int lastTime = 0;

		for (int i = 0; i < size; i++) {
			meetings.add(new TimeTable(br.readLine()));
		}
		meetings.sort(new Comparator<TimeTable>() {
			@Override
			public int compare(TimeTable o1, TimeTable o2) {
				if (o1.end == o2.end) {
					return o1.start - o2.start;
				}
				return o1.end - o2.end;
			}
		});

		for (TimeTable meeting : meetings) {
			if (lastTime <= meeting.getStart()) {
				lastTime = meeting.getEnd();
				count++;
			}
		}
		System.out.println(count);
	}

	private static class TimeTable {
		private final int start;
		private final int end;

		public TimeTable(String times) {
			String[] split = times.split(" ");
			this.start = Integer.parseInt(split[0]);
			this.end = Integer.parseInt(split[1]);
		}

		public int getStart() {
			return start;
		}

		public int getEnd() {
			return end;
		}
	}
}

성공