Softeer Level 2 GBC Python

문제 링크

https://softeer.ai/practice/6270

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
limits = []
buildingHeight = 0
for _ in range(n):
  height, speed = map(int, input().split())
  buildingHeight += height
  limits.append((buildingHeight, speed))

nowHeight = 0
speeds = []
maxDiff = 0
for _ in range(m):
  height, speed = map(int, input().split())
  nowHeight += height
  speeds.append((nowHeight, speed))

prevHeight = 0
for i in range(m):
  currentHeight, currentSpeed = speeds[i]
  if i > 0:
    prevHeight = speeds[i-1][0]
  for j in range(n):
    limitHeight, limitSpeed = limits[j]
    if prevHeight >= limitHeight:
      continue
    currentDiff = currentSpeed - limitSpeed
    if currentDiff > maxDiff:
      maxDiff = currentDiff
    if limitHeight >= currentHeight:
      prevHeight = limitHeight
      break

print(maxDiff)

풀이 방법

- 테스트 높이와 제한 속도 높이를 누적으로 저장했다.

- 저장한 데이터를 바탕으로 전 테스트 높이가 제한 속도 높이보다 작거나 같으면 다음 제한 속도 높이로 이동하게 만들었다.

- 해당 높이가 유효하면 prevH > limitH 이면 현재 속도 차이를 계산해서 maxDiff와 비교하면 된다.

느낀점

- 브루트포스 방식인데 이걸 그리디로 착각했다.

- 전에 풀었는데 소프티어 사이트 개선하면서 푼 기록이 사라졌기에 다시 풀어봤는데 왜 이렇게 오래 걸렸는지 모르겠다.