[백준] 🥈 2563 회의실 배정

📌 난이도

🥈 Silver 1

📌 문제

https://www.acmicpc.net/problem/1931

📌 풀이

와 이전 문제에서 느꼈던, Greedy 알고리즘이 쉽다는 생각을 처참하게 깨준 문제였다.

처음에는 Conference[][]에 시작 시간과 끝나는 시간을 넣고, for문을 돌려서 i번째 시간부터 시작을 해서, 이후에 올 수 있는 가장 가까운 시작시간을 붙혀서 개수를 구했다.
이것을 처음부터 끝까지의 개수를 max쳐서 구했는데 당연하게도 틀렸다.

곰곰히 생각해보니까 이런식으로 문제점이 하나가 있었다.

위와 같이 1-4와 2-3이 있으면 해결이 안되는 방법이었다.

대체 이걸 어떻게 풀어야하나 고민하다가 앞에서 다른 애한테 설명해주시는 선배님이 정렬을 설명하시길래 아~! 정렬을 써야하는 문제구나! 싶어서, 시작 시간을 기준으로 정렬을 하였다.
이후 이전과 같이 풀었다.

하지만 이렇게 정렬을 시켰음에도 불구하고, 위의 경우와 같이 분명 가장 많은 시간을 잡는 경우는 첫번째 회의 이후 5, 6번째 회의를 하는 경우인데, 내 알고리즘으로는 이것을 해결할 수가 없었다.
이런 경우 수를 고려하려고 하니까 해결이 안되는 방식이였다.

정말 많은 고민을 하였다.
그러다 문뜩 생각난 사실이 뒤로 정렬을 하면 어떻게 될까라는 것이였다.

위 그림과 같이 뒤를 기준으로 정렬을 하자, 자동으로 길이가 긴 회의시간들은 짧은 것에 비해 후순위로 배치되게 되어서, 경우의 수를 고려하지 않아도 되게 되었다.

너무 신기하였다.

역시 코딩 문제는 많이 풀어서 경험을 쌓아야만 하는 것 같다.

📌 Code

package Greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class N1931 {
    public static int count;
    public static int[][] conference;
    public static int[][] conference2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        count = Integer.parseInt(st.nextToken());

        conference = new int[count][2];

        for (int i = 0; i < count; i++) {
            st = new StringTokenizer(br.readLine());
            conference[i][0] = Integer.parseInt(st.nextToken());
            conference[i][1] = Integer.parseInt(st.nextToken());
        }

        SortConference();
        System.out.println(MaxConference());
    }

    public static void SortConference() {
        Arrays.sort(conference, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });
    }

    public static int MaxConference() {
        int result = 1;
        int time = conference[0][1];
        for (int i = 1; i < count; i++) {
            if (conference[i][0] >= time) {
                time = conference[i][1];
                result += 1;
            }
        }
        return result;
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁