[Softeer] GBC (level 2)

사용 언어: Python3

문제

GBC

풀이

내 풀이

import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())

limit, test = [], []

start, end = 0, 0
for _ in range(N):
    a, v = map(int, input().rstrip().split())
    start = end
    end = start + a
    limit.append((start, end, v))

start, end = 0, 0
for _ in range(M):
    a, v = map(int, input().rstrip().split())
    start = end
    end = start + a
    test.append((start, end, v)) # ✅ (s,e,v) 형식으로 변경

mx = 0
for x in test: # x[0]: start, x[1]: end, x[2]: velocity
    for y in limit:
        if (x[1]-x[0]) + (y[1]-y[0]) > max(x[1], y[1]) - min(x[0], y[0]): # ✅ 포함관게 판별
            mx = max(mx, x[2]-y[2]) # 속도차이 max 갱신
print(mx)

• 정답!
• 떠올린 아이디어는 아래와 같다.
  1. test와 limit 각각, 구간 길이를 통해 시작지점와 종료지점을 알아낸다.
  2. test의 시작지점과 종료지점 사이에 겹치는 limit 구간을 구한다. (하나의 test 구간에 여러 limit 구간들이 겹칠 수 있다.)
  3. 2번에서 구한 겹치는 limit 구간들과 test 구간과의 속도차를 계산한다.
  4. 3번에서 구한 속도차이 중 최댓값이 정답이다.

  

• 문제를 풀기 위해 두 가지 핵심 로직이 있다.
  • (길이, 속도) -> (시작지점, 종료지점, 속도) 형식으로 변경
  • 포함관계 판별 두(limit, test) 구간 길이의 합 > max(limit, test) - min(limit,test) 을 만족하면, 겹치는 부분이 존재하는 것이다.
    

다른 풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

limit_speed = [0] * 101 # ✅ 구간별 제한 속도 저장
pos = 1 # 현재 위치
for i in range(N):
    l, v = map(int, input().rstrip().split()) # length, velocity
    for j in range(pos, pos+l):
        limit_speed[j] = v
    pos += l

mx = 0
pos = 1 # 현재 위치 리셋
for i in range(M):
    l, v = map(int, input().rstrip().split())
    for j in range(pos, pos+l):
        mx = max(mx, v - limit_speed[j])
    pos += l
print(mx)

• 101칸짜리 배열을 만들어서 구간에 따른 제한 속도를 저장한 뒤, test를 순회하며 max 값을 갱신하는 풀이이다.
• 참고
  • 블로그

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기