문제 분석
문제
문제를 간단하게 요약해보자면 나무가 n그루가 주어지고 n개의 나무의 위치가 주어진다. 그리고 q번을 찍어 각각 점수를 매기는데 사진을 찍은 위치에서 각 나무까지 거리의 합을 점수로 받는다고 한다.
입력, 출력
문제에 대한 입력, 출력을 보게 되면 첫번째 줄에서는 n, q의 값을 받는다고 한다. 그리고 이후에 나무의 위치가 차례대로 주어지고 q개의 줄에 촬영 위치가 주어진다.
이후 출력에서는 촬영위치를 입력할 때마다 이에 대한 점수를 출력해주어야 한다.
예제
예제 입력은 다음과 같다.
그리고 문제 분류를 한번 살펴보게 되면 두가지가 있다
누적합과 이분탐색.
이를 이용해서 풀 수 있다.
코드 분석
mid 값 찾기
def check(peo):
left=1
right=n
mid=0
while left <= right:
mid = (left+right) // 2
if tree[mid]>peo:
right = mid - 1
elif tree[mid]<peo:
left = mid + 1
else:
break
return mid먼저 문제를 풀기 위해서는 mid 값을 찾아야 한다. mid값이라는 것은 q개의 줄에 걸쳐서 사진 찍는 위치가 주어지는데 이 위치가 어디에 있는지 찾아주어야 한다. 이를 위해 이진탐색을 이용하게 된다.
left, right를 이용해 mid 값이 기준값(촬영위치)보다 큰지 작은지에 따라서 기준점을 찾아지고 그 외에 경우에는 탈출하도록 해서 mid값을 리턴해준다.
누적합을 이용한 값 구하기
for i in range(q):
now=int(input())
mid = check(now)
if tree[mid]<=now:
left_res = mid * now - tree_sum[mid]
right_res = (tree_sum[n] - tree_sum[mid]) - (n-mid)*now
else:
left_res = (mid - 1)*now - tree_sum[mid - 1]
right_res = (tree_sum[n]-tree_sum[mid-1])-(n-mid+1)*now
print(left_res+right_res)q개의 줄에 걸쳐서 값을 입력 받는다. 매번 새롭게 받아 들이기 때문에 리스트로 받을 필요 없이 변수로 입력받으면 된다.
그리고 mid 값은 앞에 다룬 것을 함수호출해 찾아낸다.
마지막 if, else 부분이 가장 생각해내기가 어려웠다.
이 부분에 대한 구조를 짜다가 시간초과를 받았었는데 시간복잡도를 줄이기 위해 누적합을 이용하는 방식이다.
if, else로 나누어서 하는 이유는 tree의 mid 위치에 있는 값이 촬영위치보다 같거나 큰 경우, 작은 경우로 나누어지기에 이에 맞춰서 해당 값이 어디로 들어가냐에 따라 넣는 인덱스가 달라지기 때문이다.
left는 왼쪽 부분만 구하기 때문에 촬영위치보다 작을 수 밖에 없고 '촬영위치왼쪽에 위치한 값 개수 - 왼족위치한 값들의 누적합'으로 구해줄 수 있다. right는 오른쪽 부분인데 왼쪽에 해당하는 값들을 빼주어야 한다. 그래서 '전체 누적합-중앙까지의 누적합'에서 '(전체-중앙까지의 인덱스)촬영위치'를 빼주게 되면 이에 대한 값이 나온다.
이 두 값을 합치게 되면 결과가 나오게 된다.
결론
문제 분류를 이용해 약간의 방향성을 잡았지만 시간 복잡도를 줄이는 방법에 대해서 생각해내는 것이 조금 까다로웠던 문제라고 생각한다. 머릿속에 어느정도는 이 과정을 그려냈지만 어떻게 구현해야할지에 대해서 도출해내지 못했기 때문이다. 잊어가고 있었던 이분탐색, 누적합에 대해서 다시 복습할 수 있었던 문제라고 생각한다.
