GBC

이 구간에서 제한 속도를 벗어나면(즉 제한속도를 초과하면) 서버에 초과한만큼의 속도가 로그에 남는다. 불행하게도 현재 서버의 상태가 off 상태임으로 광우는 서버의 데이터를 받아볼 수가 없다. 광우는 임의의 구간의 길이와 속도를 정하여 시범운행 할 때, 가장 제한 속도가 크게 벗어난 값을 스스로 구해야 한다. M개의 구간을 검사한다고 할 때 예를 들면,

첫 번째 구간의 운행 길이는 60m 이고 속도는 76m/s

두 번째 구간의 운행 길이는 18m 이고 속도는 28m/s

세 번째 구간의 운행 길이는 22m 이고 속도는 50m/s

이라고 했을 때 제한 속도를 벗어나 가장 차이가 큰 속도를 구해 보자.

첫번째 구간 50m 까지에서 제한 속도와 실제 운행 속도를 비교했을 때, 제한 속도를 26m/s 초과했다.

이후 두번째 구간과 실 운행한 첫번째 구간이 10m 정도 겹치는데, 이때 제한 속도를 36m/s 초과하게 된다.

그 이후 구간들에서는 차이가 그보다 크지 않으므로 가장 큰 속도 차이는 36m/s임을 알 수 있다.

주어진 구간의 제한속도와 광우가 테스트한 구간의 속도를 기준으로 가장 크게 제한 속도를 넘어간 값이 얼마인지 구해보자.

입력

첫 줄에 N과 M이 주어진다. 그 다움 줄부터 N개의 줄은 각 구간의 길이 및 해당 구간에서의 제한 속도가 주어지며, 다음 M개의 줄은 광우가 테스트하는 구간의 길이와 속도가 주어진다.

출력

광우가 시범운행을 하는 동안 제한 속도를 가장 크게 벗어난 값을 출력 한다. 단 제한 속도를 벗어나지 않은 경우는 0을 출력 한다.

예시1

입력

Plain Text
복사

출력

Plain Text
복사

예시2

입력

Plain Text
복사

출력

Plain Text
복사

정답

solution 1.

import sys

N, M = list(map(int, sys.stdin.readline().split()))

origin = []   # 실제
for _ in range(N):
    l, s = list(map(int, sys.stdin.readline().split()))
    origin.extend([s for _ in range(l)])    # 길이만큼 속도를 붙임 (ex. 길이가 50, 속도가 40이면 40을 50개 붙임)

test = []     # 시범 운행
for _ in range(M):
    l, s = list(map(int, sys.stdin.readline().split()))
    test.extend([s for _ in range(l)])

answer = 0   # 최대 초과 속도
for i in range(100):    # 0에서부터 100개 1대1로 살펴보기
    if test[i] > origin[i]:     # test의 속도가 더 빠른 경우
        answer = max(answer, test[i]-origin[i])   # 현재 answer와 비교하여 초과 속도가 answer보다 크다면 저장
print(answer)
Python
복사

solution 2.

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().split()))

origin = deque()
for _ in range(N):
    origin.append(list(map(int, sys.stdin.readline().split())))

test = deque()
for _ in range(M):
    test.append(list(map(int, sys.stdin.readline().split())))

answer = 0
origin_len, origin_speed = origin.popleft()
test_len, test_speed = test.popleft()
while True:

    if origin_len > test_len:     # 만약 현재 남은 원래 구간이 현재 남은 시범 운행 구간이 길다면
        origin_len = origin_len-test_len    # 현재 남은 원래 구간에서 시범 운행 길이만큼 빼기
        if origin_speed < test_speed:       # 그리고 test_speed가 더 빠르다면
            answer = max(answer, test_speed-origin_speed)   # 초과 속도 반영
        test_len, test_speed = test.popleft()    # 시범운행 덱에서 pop
    if origin_len < test_len:    # 만약 현재 남은 원래 구간이 현재 남은 시범 운행 구간보다 짧다면
        test_len = test_len-origin_len     # 현재 남은 시범 운행 구간에서 원래 구간만큼 빼기
        if origin_speed < test_speed:      # 그리고 test_speed가 더 빠르다면
            answer = max(answer, test_speed-origin_speed)   # 초과 속도 반영
        origin_len, origin_speed = origin.popleft()
    if origin_len == test_len:   # 남은 길이가 같다면
        if len(origin) > 0:      # 아직 끝까지 도달하지 않은 경우
            if origin_speed < test_speed:     # test_speed가 더 빠른 경우 초과 속도 반영
                answer = max(answer, test_speed-origin_speed)
            test_len, test_speed = test.popleft()         # 두 덱에서 모두 꺼내기
            origin_len, origin_speed = origin.popleft()
        else:                    # 끝까지 도달한 경우이다.
            if origin_speed < test_speed:     # test_speed가 더 빠른 경우 초과 속도 반영
                answer = max(answer, test_speed-origin_speed)
            break                # 끝

print(answer)
Python
복사

풀이

solution 1.

•

구간의 총 합이 정해져있고 구간별 구간의 길이와 제한 속도가 모두 양의 정수이기 때문에 사용할 수 있는 방법이다.

•

1m 단위로 구간의 길이를 쪼개고 1m마다의 제한 속도를 설정한다.

•

그리고 이를 리스트로 만들면 원소가 100개인 리스트가 나온다.

•

예를 들어 구간의 길이와 제한 속도가 다음과 같이 주어질 때 만들어지는 리스트는 다음과 같다.

[구간의 길이, 제한 속도]

[50, 50]

[40, 40]

[10, 30]

→ [50, 50, 50, ……, 40, 40, 40, ….., 30, 30, …..] → 50 * 50 + 40 * 40 + 30 * 10

origin = []   # 실제
for _ in range(N):
    l, s = list(map(int, sys.stdin.readline().split()))
    origin.extend([s for _ in range(l)])    # 길이만큼 속도를 붙임 (ex. 길이가 50, 속도가 40이면 40을 50개 붙임)

test = []     # 시범 운행
for _ in range(M):
    l, s = list(map(int, sys.stdin.readline().split()))
    test.extend([s for _ in range(l)])
Python
복사

•

그러므로 원래 구간에 대한 제한 속도를 담은 리스트를 하나 만들고 시범 운행을 한 구간과 속도를 담은 리스트를 만든 다음 첫 번째 원소부터 100번째 원소까지 1대1로 비교하면 엘레베이터가 올라가면서 제한 속도를 위반했는지, 그리고 얼마나 위반했는지를 알 수 있다.

answer = 0   # 최대 초과 속도
for i in range(100):    # 0에서부터 100개 1대1로 살펴보기
    if test[i] > origin[i]:     # test의 속도가 더 빠른 경우
        answer = max(answer, test[i]-origin[i])   # 현재 answer와 비교하여 초과 속도가 answer보다 크다면 저장
print(answer)
Python
복사

solution 2.

•

덱을 이용하는 방법이다.

•

구간의 길이와 제한 속도 또는 그냥 속도를 담은 덱을 만들고 계속 pop을 해가면서 문제를 해결한다.

origin = deque()
for _ in range(N):
    origin.append(list(map(int, sys.stdin.readline().split())))

test = deque()
for _ in range(M):
    test.append(list(map(int, sys.stdin.readline().split())))

answer = 0
origin_len, origin_speed = origin.popleft()
test_len, test_speed = test.popleft()
Python
복사

•

만약 현재 pop 되어 있는 원래 구간의 길이보다 pop 되어 있는 시범 운행의 길이가 더 짧다면 다음 시범 운행 구간과 걸쳐 있다는 의미이다. 따라서 얼마나 걸쳐 있는지를 확인하기 위해서 현재 남아 있는 원래 구간의 길이를 업데이트 하고 그 다음 시범 운행 데이터를 pop해야 한다. 물론 그 전에 초과 속도를 체크해서 현재 기록되어있는 최대 초과 속도보다 크다면 업데이트해준다.

answer = 0
origin_len, origin_speed = origin.popleft()
test_len, test_speed = test.popleft()
while True:

    if origin_len > test_len:     # 만약 현재 남은 원래 구간이 현재 남은 시범 운행 구간이 길다면
        origin_len = origin_len-test_len    # 현재 남은 원래 구간에서 시범 운행 길이만큼 빼기
        if origin_speed < test_speed:       # 그리고 test_speed가 더 빠르다면
            answer = max(answer, test_speed-origin_speed)   # 초과 속도 반영
        test_len, test_speed = test.popleft()    # 시범운행 덱에서 pop
Python
복사

•

반대로 시범 운행의 길이가 더 길다면 다음 원래 구간과 걸쳐 있다는 의미이다. 따라서 위와 반대 방식으로 해주면 된다.

if origin_len < test_len:    # 만약 현재 남은 원래 구간이 현재 남은 시범 운행 구간보다 짧다면
	test_len = test_len-origin_len     # 현재 남은 시범 운행 구간에서 원래 구간만큼 빼기
	if origin_speed < test_speed:      # 그리고 test_speed가 더 빠르다면
		answer = max(answer, test_speed-origin_speed)   # 초과 속도 반영
		origin_len, origin_speed = origin.popleft()
Python
복사

•

만약 남아있는 두 구간의 길이가 같다면 경우의 수는 두 가지이다.

◦

끝이 나서 같은 경우

◦

우연히 딱 맞아 떨어진 경우

•

만약 우연히 딱 맞아 떨어진 경우 아직 덱에 구간이 남아있을 것이다. 따라서 덱을 체크해서 길이가 0 이상이라면 두 덱에서 모두 pop을 진행해준다. 물론 그 전에 초과 속도도 반영해준다.

if origin_len == test_len:   # 남은 길이가 같다면
	if len(origin) > 0:      # 아직 끝까지 도달하지 않은 경우
		if origin_speed < test_speed:     # test_speed가 더 빠른 경우 초과 속도 반영
			answer = max(answer, test_speed-origin_speed)
			test_len, test_speed = test.popleft()         # 두 덱에서 모두 꺼내기
      origin_len, origin_speed = origin.popleft()
Python
복사

•

반대로 끝이 나서 같은 경우엔 덱에 구간이 남아있지 않은 경우이다. 이 경우에는 초과 속도만 반영해주고 break 해줘서 while 문을 탈출한다.

else:                    # 끝까지 도달한 경우이다.
		if origin_speed < test_speed:     # test_speed가 더 빠른 경우 초과 속도 반영
			answer = max(answer, test_speed-origin_speed)
			break                # 끝
Python
복사

•

마지막으로 저장되어 있는 최대 초과 속도를 출력한다.

print(answer)
Python
복사