그리디 알고리즘과 정렬(백준 알고리즘 4055번)

♠ 그리디 알고리즘의 정의

 

https://jy-deeplearning.tistory.com/64

그리디 알고리즘(백준 알고리즘 11399)

 

그리디 알고리즘은 매 선택에서 지금 당장 최적인 답을 선택하여 적합한 결과를 도출하려는 알고리즘 설계 기법이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 종합적으로 보았을 때는 최적이라는 보장이 없다. 

 

 

♠ 문제 이해(백준 알고리즘 4055번)

 

이 문제는 아람이가 아침 8시부터 자정까지 열리는 파티들을 최대한 많이 참석하게 하려는 문제이다. 파티에는 최소 30분은 있어야 하며 아람이는 축지법을 쓰기 때문에 파티 간 이동시간은 신경쓰지 않아도 된다. 

 

처음 이 문제를 읽었을 때는 최대한 많이 들을 수 있는 수업의 수를 찾는 것처럼 전형적인 DP문제인 줄 알았다. 그런데 중요한 것은 중간에 빠져나갈 수 없는 수업과 달리, 파티는 30분만 참석하고 나갈 수 있다는 것이다. 즉 8시에 시작하는 파티가 두 개 있다면 두 개의 파티에 모두 참석할 수 있다. 첫 번째 파티에는 8시부터 8시 30분까지 참석하고 두 번째 파티에는 8시 30분부터 9시까지 참석하면 되기 때문이다. 최대한 많은 파티에 참석해야 하기 때문에 30분씩만 파티에 참석하는 것이 효율적이다. 따라서 이 문제는 각 시간대별로 참석할 수 있는 파티를 체크하여 최대한 큰 값을 구하는 그리디 알고리즘을 사용하면 된다. 

 

 

♠ 정렬을 사용한 시행착오

 

1. 파티의 시작 시간을 기준으로 정렬을 사용한 방법

 

처음에는 주어진 파티를 시작하는 시간을 기준으로 정렬하여 참석할 수 있는 파티의 수를 구하고자 했다. 현재 시간을 current로 하여 파티에 참석하기 시작한 시간을 기준으로 30분씩 더해갔다. 

 

예제 입력에서 8개의 파티가 주어진 경우를 보았을 때, 파티를 시작하는 시간을 기준으로 정렬하면 아래와 같다. 

[[9, 10], [9, 10], [9, 11], [12, 13], [12, 13], [12, 13], [12, 14], [13, 14]]

 

첫 파티는 9시에 시작하므로 처음의 current 는 9로 설정하였다. 그런 뒤 party를 하나씩 꺼내어서 현재 시간보다 파티의 종료 시간이 30분 이상 늦으면(예를 들어 현재의 시간이 9시인데 비교하는 파티가 이보다 30분 이상 늦은 9시 30분 이후에 끝나는 파티라면) 참석할 수 있는 파티라고 판단하여 파티의 수를 늘려갔다. 

 

또한 파티에 참석한 뒤의 상황을 고려하여 current를 늘려갔는데, 여기서 중요한 것은 무조건 30분씩 더하는 것이 아니라 현재 비교하고 있는 파티의 시작 시간을 고려해야 한다는 것이다. 

 

예를 들어 위의 예시에서 첫 번째 파티([9, 10])을 참석하고 나면 current = 9.5, 이어서 두 번째  파티([9, 10])를 참석하고 나면 current = 10, 세 번째 파티([9, 11])를 참석하고 나면 current = 10.5 이다. 이렇게 파티의 시작 시간이 current와 같거나 current보다 작으면 current에 0.5를 더해주면 된다. 하지만 네 번째 파티([12, 13])에 참석하려고 할 때 문제가 생긴다. 세 번재 파티에 참석한 이후에 current 가 10.5 이기 때문에 아직 네 번째 파티에 참석할 수 있는 시간이 아닌 것이다. 이렇게 current보다 늦게 시작되는 파티에 참석하게 되면 current는 '늦게 시작되는 파티의 시작 시간 + 0.5' 가 되어야 한다. 네 번째 파티에 참석하고 나면 current 는 11 이 아니라 12.5가 되는 것이다. 

import sys
input = lambda: sys.stdin.readline().rstrip()
day = 0

while True:
	p = int(input())
	if p==0:
		break
	day +=1
	party = []
	
	for i in range(p):
		new = list(map(int, input().split()))
		party.append(new)
		
	party = sorted(party)
	
	total, current = 0, party[0][0]
	for item in party:
		if item[1] - current >= 0.5:
			total+=1 
			if item[0] > current:
				current = item[0] + 0.5 
			else:
				current += 0.5
                
	print(f"On day {day} Emma can attend as many as {total} parties.")

 

이 코드를 이용하면 예제를 모두 해결할 수 있다. 하지만 아래와 같은 경우 문제가 생긴다. 

 

[예제]

7
8 9
8 9
9 10
9 10
10 11
8 11
10 12

 

[정렬된 파티]

[[8, 9], [8, 9], [8, 11], [9, 10], [9, 10], [10, 11], [10, 12]]

 

위와 같이 시작 시간을 기준으로 파티를 정렬할 경우, 참석할 수 있는 파티는 아래와 같다. 

파티	[8, 9]	[8, 9]	[8, 11]	[9, 10]	[9, 10]	[10, 11]	[10, 12]
current	8.5	9	9.5	10	10 (불참)	10.5	11
total	1	2	3	4	4	5	6

 

하지만 실제로는 7개 파티 모두에 참석할 수 있다. 

파티	[8, 9]	[8, 9]	[9, 10]	[9, 10]	[8, 11]	[10, 11]	[10, 12]
current	8.5	9	9.5	10	10.5	11	11.5
total	1	2	3	4	5	6	7

 

파티의 시작 시간을 기준으로 정렬하다 보니 일찍 시작해도 늦게 끝나는 파티는(위의 경우 [8, 11]) 좀 늦게 가고 일찍 끝나는 파티를 먼저 가야 하는데 무조건 일찍 시작하는 파티부터 가게 되어 나타나는 문제이다. 

 

 

 

2. 파티가 끝나는  시간을 기준으로 정렬을 사용한 방법

 

파티의 시작 시간을 기준으로 정렬했을 때 틀렸기 때문에 끝나는 시간을 기준으로 정렬해야 하는구나 싶어서 정렬 방법을 바꾸었다. 나머지는 모두 이전과 같다. 

import sys
input = lambda: sys.stdin.readline().rstrip()
day = 0

while True:
	p = int(input())
	if p==0:
		break
	day +=1
	party = []
	
	for i in range(p):
		new = list(map(int, input().split()))
		party.append(new)
		
	party = sorted(party, key = lambda x:x[1])
	
	total, current = 0, party[0][0]
	for item in party:
		if item[1] - current >= 0.5:
			total+=1 
			if item[0] > current:
				current = item[0] + 0.5 
			else:
				current += 0.5
	print(f"On day {day} Emma can attend as many as {total} parties.")

 

끝나는 시간을 기준으로 했더니 앞에서는 틀렸던 입력값에서 정답이 출력되었다. 하지만 이  코드 역시 틀렸는데, 또다른 예외가 있었기 때문이다. 

 

[예제]

10
11 14
13 15
8 9
13 14
14 15
9 12
13 14
11 14
13 15
12 13

 

[정렬된 파티]

[[8, 9], [9, 12], [12, 13], [11, 14], [11, 14], [13, 14], [13, 14], [13, 15], [14, 15], [13, 15]]

 

파티가 끝나는 시간을 기준으로 정렬할 경우, 참석할 수 있는 파티는 아래와 같다. 

파티	[8, 9]	[9, 12]	[12, 13]	[11, 14]	[11, 14]	[13, 14]	[13, 14]	[13, 15]	[14, 15]	[13, 15]
current	8.5	9.5	12.5	13	13.5	14	14 (불참)	14.5	15	15 (불참)
total	1	2	3	4	5	6	6	7	8	8

 

하지만 실제로 참석할 수 있는 파티는 아래와 같다. 

파티	[8, 9]	[9, 12]	[11, 14]	[11, 14]	[12, 13]	[13, 14]	[13, 14]	[13, 15]	[14, 15]	[13, 15]
current	8.5	9.5	11.5	12	12.5	13.5	14	14.5	15	15 (불참)
total	1	2	3	4	5	6	7	8	9	9

 

위의 표를 보면 11시에 시작하는 파티 두 개를 먼저 참석하고 그 다음 12시에 시작하는 파티를 참석하도록 순서를 바꾸면 총 9개의 파티에 참석할 수 있다. 

 

 

♠ 문제 해결

 

파티가 시작하는 시간과 끝나는 시간을 기준으로 해결하는 것이 아니라 8시부터 24시까지를 놓고 각 시간대에 참석할 수 있는 파티를 2개씩 고르는 방법을 썼다. 

[[8, 9], [8, 9], [8, 11], [9, 10], [9, 10], [10, 11], [10, 12]]

 

시간	8시	9시	10시	11시
참석할 수 있는 파티	[8, 9], [8, 9]	[9, 10], [9, 10]	[10, 11], [8, 11], [10, 12]	[10, 12]
참석할 파티	[8, 9], [8, 9]	[9, 10], [9, 10]	[10, 11], [8, 11],	[10, 12]

 

 

[[8, 9], [9, 12], [12, 13], [11, 14], [11, 14], [13, 14], [13, 14], [13, 15], [14, 15], [13, 15]]

 

시간	8시	9시	11시	12시	13시	14시
참석할 수 있는 파티	[8, 9]	[9, 12]	[11, 14], [11, 14]	[12, 13]	[13, 14], [13, 14], [13, 15]	[13, 15], [14, 15], [14, 15]
참석한 파티	[8, 9]	[9, 12]	[11, 14], [11, 14]	[12, 13]	[13, 14], [13, 14]	[13, 15], [14, 15]

 

이런 식으로 우선 파티 시작 시간을 기준으로 해당 시간에 참석할 수 있는 파티들을 모두 모은 다음 그 중 먼저 끝나는 파티들을 2개씩 뽑아서 해당 시간에 할당하면 된다. 

 

import sys
input = lambda: sys.stdin.readline().rstrip()
day = 0

while True:
	p = int(input())
	if p==0:
		break
	day +=1
	party = []
	
	for i in range(p):
		new = list(map(int, input().split()))
		party.append(new)

	party = sorted(party)
	
	total = 0 
	for i in range(8, 24):
		candidates = []
		for item in party:
			if item[0] <= i and item[1]>=i+1:
				candidates.append(item)
		candidates = sorted(candidates, key=lambda x:x[1])
		# print(i, candidates)
		
		if len(candidates)>1:
			selected = candidates[:2]
			party.remove(selected[0])
			party.remove(selected[1])
			total +=2 
		elif len(candidates)==1:
			selected = candidates
			party.remove(selected[0])
			total += 1
		# print(party, total)
	print(f'On day {day} Emma can attend as many as {total} parties.')

 

파티 시작 시간을 기준으로 해당 시간에 참석할 수 있는 파티들을 모으기 위해 파티 시작 시간을 기준으로 정렬하였다. 파티 진행이 가능한 8시부터 24시까지를 범위에 넣고 각 파티들이 해당 시간에 참석할 수 있는 파티(item[0] <= i, item[1] > i+1 => 시작 시간은 해당 시간인 i보다 빠르거나 같아야 하고 끝나는 시간은 i+1과 같거나 그보다 늦어야 함)이면 후보(candidates) 에 넣고 이를 끝나는 시간을 기준으로 정렬하였다. 

 

해당 시간에 참석할 수 있는 파티가 2개 이상이면 끝나는 시간이 빠른 앞의 두 개 파티를 참석한 것으로 보고 전체 파티에서 제거하였고, 참석할 수 있는 파티가 1개인 경우 한 개 파티만 제거하였다. 

 

이 문제에서는 파티가 최대 100개뿐이라서 for문을 이용하여 파티를 여러 번 돌았는데, 시작 시간으로 정렬했으므로 item[0]이 i보다 큰 경우부터는 돌지 않도록 하면 효율성을 높일 수 있을 것 같다.