그리디 알고리즘(백준 알고리즘 1931번)

♣ 그리디 알고리즘 문제 해결의 조건

1. 각 단계에서 최선의 선택을 해야 한다. 

2. 최적의 부분 구조를 만들어야 한다. 즉 전체 문제를 작은 부분으로 나누어 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것이다. 

 

 

♣ 백준 알고리즘 1931번 

 

이 문제는 N개의 회의에 대해 회의를 가장 많이 할 수 있는 최대 횟수를 구하는 문제이다. 

 

 

♣ 문제 해결

먼저 주어진 회의가 끝나는 시간을 기준으로 회의들을 정렬한다. 회의가 끝나야 다음 회의가 들어올 수 있으므로 끝나는 시간을 기준으로 정렬하면 각 회의들의 부분 구조를 만들 수 있다. 시작 시간에 관계 없이 빠르게 끝나는 회의를 먼저 선택해야 회의를 조금이라도 더 많이 진행할 수 있기 때문이다. 회의가 끝나는 시간을 기준으로 정렬하되, 끝나는 시간이 같으면 시작 시간이 빠른 것을 앞으로 놓는다. 

 

위의 코드에 따르면 meetings는 다음과 같이 정렬된다. 

 

회의를 정렬한 뒤, 첫 회의부터 하나씩 돌아가면서 조건을 따지기 시작한다. 처음에 end_time을 0으로 설정하고, 시작 시간이 이보다 늦는 회의가 있으면 그 회의를 선택하여 추가한다. 즉 현재 회의가 끝난 시간과 다음 회의가 시작하는 시간이 같거나 크면 다음 회의를 추가하는 것이다. 

 

 

arr의 변화는 아래와 같다. 

 

위의 회의들에서 가장 많이 선택할 수 있는 수는 (1, 4), (5, 7), (8, 11), (12, 14) 로 4개이다. 

크게 어렵지는 않지만 의존적이지 않은 부분 구조를 만들기 위해  '끝나는 시간'을 기준으로 정렬하는 것이 중요하다. 

 

전체 코드