[백준] 1931번 - 회의실 배정
1차 시도
T = int(input()) # 회의의 수
start, end, cnt = 0,0,0
for i in range(T):
A, B = map(int,input().split())
if (end <= A):
start = A
end = B
cnt += 1
print(cnt)
T개의 회의를 입력받을 때 순서대로 회의가 시작된다고 생각했다.
T개의 회의는 입력 순서대로 시작되는 것이 아니므로 입력받은 회의들을 먼저 오름차순으로 sorting할 필요가 있음
-> 또한, 만약 (1,10), (2,2), (3,5) 이런 회의들이 있을 때 끝나는 시간 기준으로 sorting을 하지 않을 경우, (1,10)이 먼저 회의를 점령하면 나머지 뒤에 회의들은 진행될 수 없다. 따라서 최대로 많은 회의를 진행해야 함으로 끝나는 시간 기준 sorting작업이 필요하다.
2차 시도
T = int(input()) # 회의의 수
start, end, cnt = 0,0,0
lst = []
for i in range(T): # T개의 회의를 입력받고 회의들을 lst에 저장한다.
A, B = map(int,input().split())
lst.append([A,B])
lst.sort(key=lambda x : (x[1],x[0])) # 끝나는 시간을 기준으로 오름차순함 정렬한 뒤, 시작하는 시간으로 오름차순 정렬
for i in range(T):
if (lst[i][0] == lst[i][1]):
cnt += 1
elif (end <= lst[i][0]):
start = lst[i][0]
end = lst[i][1]
cnt += 1
print(cnt)
25%정도에서 틀렸습니다가 나온다.
질문에 있는 반례들로 테스트해봐도 잘 나오는데 어떤 부분이 문제인지 잘 모르겠음
lst.sort(key = lambda x: (x[1],x[0]))
-> (x[1], x[0]) 끝나는 시간 기준으로 먼저 sorting 후, 시작하는 시간 기준으로 sorting한다.
최종 코드
T = int(input()) # 회의의 수
start, end, cnt = 0,0,0
lst = []
for i in range(T): # T개의 회의를 입력받고 회의들을 lst에 저장한다.
A, B = map(int,input().split())
lst.append([A,B])
lst.sort(key=lambda x : (x[1],x[0])) # 끝나는 시간을 기준으로 오름차순함 정렬한 뒤, 시작하는 시간으로 오름차순 정렬
for i in range(T):
if (end <= lst[i][0]):
end = lst[i][1]
cnt += 1
print(cnt)
굳이 조건을 더 걸어줄 필요가 없었음...끝나는 시간을 기준으로 오름차순 정렬한 뒤, 시작하는 시간을 기준으로 오름차순 정렬하면 무조건 (4,4)와 같이 시작시간과 끝나는 시간이 같은 회의들은 카운팅이 진행된다.
Author And Source
이 문제에 관하여([백준] 1931번 - 회의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yerimstar/백준-1931번-회의실-배정저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)