(BOJ2594 놀이공원

• tags : (algorithm

  No matching post could be found

  - (sweeping
• 문제 링크 : https://www.acmicpc.net/problem/2594
• 풀이 링크
  • Python

• 시간을 활용하는 문제
• 주어진 시간을 제외한 시간 중, 연속된 최고 시간을 선택한다.
• 아마 두가지 방법 정도가 있을 것 같은데,
  • 첫 번째는 주어지는 시간이 최대 60 * 10분이므로, 해당 길이 배열을 생성 후 확인 할 수 있고
  • 다른 방법은 시간을 정렬, 스위핑을 통하여 비어있는 시간 중 최대 시간을 뽑아낼 수 있다.
• 이 문제는 스위핑으로 해결했다.

• 시간을 HHMM형식이 아니라 전부다 분으로 바꿨으면 더욱 편리하게 해결했을 것 같다.

schedules = []
for _ in range(N):
    st, end = map(int, input().split())
    if st % 100 < 10:
        st = st - 100 + 50
    else:
        st -= 10
    if end % 100 >= 50:
        end = end + 100 - 50
    else:
        end += 10
    schedules.append((st, end))
schedules.sort()

• 일정을 하나씩 받으면서,
  • 주어진 문제에 따라 시작 시간 10분전부터, 종료시간 10분후까지 불가능하므로
  • 조건을 계산 한 후 일정표 리스트에 추가, 정렬한다.

ans = 0
time = 1000
for st, end in schedules:
    if time < st:
        ans = max(ans, get_time_diff(time, st))
    if time < end:
        time = end
else:
    if time < 2200:
        ans = max(ans, get_time_diff(time, 2200))

• 스위핑 알고리즘은 간단하게 구현할 수 있다.
• 시작 시간 1000부터 시작하여
  • 일정의 시작, 끝시간을 하나씩 확인하고,
  • 지금 가리키고 있는 시간과 다음 시작 시간 사이 시간이 있다면 정답이 될 수 있는지 확인,
  • 지금 가리키고 있는 시간보다 다름 종료 시간이 더 늦다면 가리키는 시간을 변경한다.