[코드트리 조별과제] LR Technique / 마라톤 중간에 택시타기 풀이(Python)
이번주는 LR Technique을 공부했습니다!
사실 Intermediate Mid(알고리즘 기본)의 Shorten time Technique를 전체적으로 살펴봤는데...., 전반적인 포인트는 미리 계산해둔 걸 이용함으로써 반복해서 계산하는 걸 줄이자! 인 것 같더라구요
약간 베이스는 전부 누적합 같은 느낌이랄까...???!?
LR Technique
[3, 6, 2, 6, 7, 5, 2] 와 같이 숫자들이 주어졌을 때,
다음 질의에 대해 답하는 프로그램을 작성해보세요.
단, 질의마다 하나의 숫자가 주어지며
해당 번째 숫자를 제외한
다른 숫자들에 대해 인접한 숫자간의 차이의 합을 구해야 합니다.
예를 들어 질의로 5가 주어졌다면
5번째 숫자인 7을 제외한 다른 숫자들을 나열하면
[3, 6, 2, 6, 5, 2]가 되므로
인접한 숫자간의 차이의 합은
|3 - 6| + |6 - 2| + |2 - 6| + |6 - 5| + |5 - 2| = 15가 됩니다.
이때 주어지는 숫자는 1초과 N 미만임을 가정해도 좋습니다.
이런 문제를 풀 때, 시간을 줄일 수 있는 테크닉이에요.
Left쪽에서의 누적합들과 Right쪽에서의 누적합들을 미리 구해두고, 그 사이 관계를 이용하겠다 이거지요~!
k번째 숫자를 제외하겠다고 한다면,
|arr[0]-arr[1]| + |arr[1]-arr[2]| + ...+|arr[k-1]-arr[k+1]| + |arr[k+1]-arr[k+2]| + ... + |arr[n-2]-arr[n-1]|
이런식으로 구해질 테니.. 중간에 하나 빠진 부분 외에는, 구하는 게 중복된다라는 점이 키포인트입니다.
그래서 L에는 왼쪽(0번쨰)부터 시작하여 특정인덱스까지 더한값들의 누적합을,
R에는 오른쪽(n-1번째)부터 시작하여 특정인덱스까지 더한값들의 누적합을 구해두자는 거죠!
그림으로 보자면 이렇습니다.
이렇게 된다면, 특정 k번째 값을 빼고 구하는 경우에
L[k-1] + |arr[k-1]-arr[k+1]| + R[k+1] 을 통해 간단히 구할 수 있게 됩니다!
이것을 LR 테크닉이라고 하는거구요~
그럼 대표문제를 풀어보며 마무리해볼게요
문제) 마라톤 중간에 택시타기
마라톤 코스는 N개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 마라톤이 끝납니다. 게으른 개발자 A는 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한 개를 몰래 건너뛰려 합니다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 티가 많이 나기 때문에 이 두 체크포인트는 건너뛰지 않으려고 합니다. 개발자 A가 체크포인트 한 개를 건너 뛰어서 마라톤을 완주하려고 할 때, 최소 거리를 구하는 프로그램을 작성해보세요. 단, 거리 계산은 택시 거리(Manhattan Distance)를 이용합니다. 택시거리란 ()과 () 지점 간의 거리를 로 계산하는 것을 의미합니다. 또한, 체크 포인트의 좌표는 겹쳐져 주어질 수도 있으며, 이 경우 개발자 A가 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰게 되며 그 점에 있는 모든 체크포인트를 건너뛰지 않음에 유의합니다.
입력 형식
첫 번째 줄에 체크포인트 N이 주어집니다.
이후 N개의 줄에 걸쳐 한 줄에 하나씩 각 번호에 해당하는 지점의 위치 (x, y)가 공백을 사이에 두고 주어집니다.
- 3 ≤ N ≤ 100,000
- -1,000 ≤ x, y ≤ 1,000
출력 형식
첫 번째 줄에 마라톤을 완주하는 최소 거리를 출력합니다.
입출력 예제
| 입력 | 출력 |
| 4 0 0 8 3 11 -1 10 0 |
14 |
풀이
import sys
input=sys.stdin.readline
n=int(input())
checks=[ list(map(int,input().split())) for _ in range(n)]
def dist(i1,i2):
return abs(checks[i1][0]-checks[i2][0])+abs(checks[i1][1]-checks[i2][1])
L=[0]*n
R=[0]*n
for i in range(1,n):
L[i]=L[i-1]+dist(i,i-1)
R[n-1-i]=R[n-i]+dist(n-1-i,n-i)
ans=R[0]
for i in range(1,n-1):
ans=min(ans,L[i-1]+R[i+1]+dist(i-1,i+1))
print(ans)
L, R에 어떤값들이 들어가는지를 생각하며 하나의 반복문 안에서 초기화했고,
거리구하는 함수를 만들어 사용했다는 게 코드의 포인트입니당
그리고 마지막에 패스할 체크포인트를 정하는 것의 범위는 1~n-2인데요, 그 이유는 0번과 n-1번(양 끝) 체크포인트는 스킵하지 않겠다고 문제에 정의되어있기 때문입니다!!
배운 점
쿼리마다, 반복되는 부분이 있다면, 미리 계산해놓는 방법이 있을까 생각해보자!
다음주도 화이팅입니닷