파이썬) 백준 알고리즘 | 12841번 : 정보대 등산

https://www.acmicpc.net/problem/12841

12841번: 정보대 등산

문제

숭실 대학교 정보 과학관은 숭실 대학교 건물 중 제일 높은 곳에 있다. 민주는 평소에 버스를 타고 이 언덕을 오르지만, 이 문제에 등장하기 위하여 오늘 하루만 걸어서 올라간다.

정보 과학관을 오르는 길은 왼쪽 길과 오른쪽 길이 있다. 민주는 처음에 왼쪽 길 맨 아래에 있고 정보 과학관을 오른쪽 길 맨 위에 있다.

정보 과학관을 오르는 길은 매우 구불구불하다.

또, 길의 중간 중간에는 횡단보도가 있다. 민주는 횡단보도를 한번만 건널 수 있다.

최소한으로 걷기 위해서 민주가 건너야 하는 횡단 보도의 번호와 걸어야 할 거리를 구해 더운 여름 민주를 도와주자!

입력

첫 번째 줄에는 지점의 개수 n 이 주어진다. (2 ≤ n ≤ 100,000)

횡단보도는 1번 지점부터 n 번 지점까지 한 개 씩 있고, 왼쪽 1번 지점에는 민주가, 오른쪽 n 번 지점에는 정보 과학관이 위치한다.

• 다음 줄에는 i 번째 지점에 있는 횡단보도의 거리 (0 < cross ≤ 100,000) 가 주어진다. (1 ≤ i ≤ n)
• 다음 줄에는 i 번째 지점에서 i+1번째 지점까지 왼쪽 길의 거리 (0 < left ≤ 100,000) 가 주어진다. (1 ≤  i ≤ n-1)
• 다음 줄에는 i 번째 지점에서 i+1번째 지점까지 오른쪽 길의 거리(0 < right ≤ 100,000) 가 주어진다. (1 ≤  i ≤ n-1)

출력

민주가 최소 길로 가기 위해 건널 횡단보도는 몇 번째 지점에 있는지 출력하고, 민주가 최소 길로 가기 위해 걸어야 하는 거리를 출력한다.

만약, 최소 거리로 갈 수 있는 지점이 여러곳이라면 번호가 낮은 지점을 출력한다.

백준 12841 '정보대 등산' 문제입니다.

쉬운 길을 좀 더 돌아가서 푼 느낌이 듭니다.

지금 안 사실이지만 list에서 insert와 pop함수는 쓰지 않는 게 좋은 것 같습니다.

시간복잡도가 O(N)이라고 하더라구요...

저는 insert를 써서 그런지 시간초과가 계속 떠서 왼쪽은 아래부터의 합, 오른쪽은 위의 나머지의 합을 구해서 횡단보도와 더해줬습니다.

import sys

N = int(sys.stdin.readline())
cross = list(map(int, sys.stdin.readline().split()))
left = list(map(int, sys.stdin.readline().split()))
right = list(map(int, sys.stdin.readline().split()))
dp_left = [0] * N
dp_right = [0] * N
left.insert(0,0)
right.insert(0,0)

sum_left = 0
sum_right = sum(right)
for i in range(N-1):
    sum_left += left[i]
    sum_right -= right[i]

    dp_left[i] = sum_left
    dp_right[i] = sum_right
dp_left[N-1] = sum(left)
dp_right[N-1] = 0


min_result = cross[0] + dp_right[0]
min_index = 0
result = []
for i in range(N):
    a = dp_left[i] + cross[i] + dp_right[i]
    if min_result > a:
        min_result = a
        min_index = i
    result.append(a)
result.append(dp_left[N-1] + cross[N-1])

print(min_index+1, min(result))