[백준/파이썬(Python), 자바(JAVA)] 회의실 배정1931 Silver1

💌문제

---

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

1931번: 회의실 배정

 

💌풀이

---

그리디 알고리즘 문제이다.

그리디 알고리즘이란, 최적의 솔루션을 찾기 위해 알고리즘의 각 단계에서 최적의 선택을 하는 수학적 최적화 기법이다.

솔루션을 반복적으로 구성하여 최적화 문제를 해결하는데 사용하며, 항상 현재 사용 가능한 최상의 값을 선택한다.

이러한 그리디 알고리즘은 구조가 단순한데, 개인적으로는 솔루션 떠올리는게 어려운 것 같다.

또한, 그리디는 간단하고 효율적이지만 항상 최적의 솔루션이 나오지는 않을 수 있다. 이럴 때는 DP등의 다른 알고리즘을 사용해야 한다.

 

아래 코드에 대한 설명은 다음과 같다.

회의 끝나는 시간과 시작 시간으로 다 정렬한다. 그래야 끝나는 시간 순으로 가장 빠른 회의를 또 잡을 수 있기 때문이다.

루프돌면서 current에 현재 회의가 들어간 끝나는 시간을 넣는다.

다음 원소에서 current<=시작시간 이라면 current에 다시 그 원소의 끝나는 시간을 넣는다.

그리고 answer에 1을 더해간다.

마지막에도 answer에 1을 더해줘야 하는데, 왜냐면 마지막으로 진행한 회의는 루프 안에서 계산이 안되었기 때문이다.

그래서 마지막으로 진행했던 회의도 answer에 넣어주기 위해서 1을 더해주는 것이다.

 

💌파이썬 코드

---

n=int(input())
meeting=[]
for i in range(n):
    meeting.append(list(map(int,input().split())))

meeting=sorted(meeting,key=lambda x:(x[1],x[0]))
answer=0
current=meeting[0][1]
for i in range(1,n):
    if current<=meeting[i][0]:
        current=meeting[i][1]
        answer+=1

print(answer+1)

💌자바 코드

---

package org.example.day4;

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

public class Meeting {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[][] meeting=new int[n][n];
        for(int i=0;i<n;i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            meeting[i][0]=a;
            meeting[i][1]=b;
        }
        int answer=0;
        int current=meeting[0][1];

        for(int i=0;i<n;i++){
            if (current<=meeting[i][0]){
                    current=meeting[i][1];
                    answer+=1;
            }
        }
        System.out.println(answer+1);
    }
}