[Softeer] 조립라인

문제링크

---

조립라인

풀이과정

---

무조건 누적합을 저장해놔서 불러오며 써야 할 수 있다고 생각했다.

그래서 입력받은 i시간의 A, B 작업 시간과 Ai → Bi+1, Bi → Ai+1 시간을 저장한다.
Ai으로 올 수 있는건 Ai-1과 Bi-1이므로 각 경우의 시간을 계산하고 그 중 작은 값을 저장한다.
Bi도 같은 방식으로 계산하면 된다. 이때 주의해야할 점은 Ai에서 Ai+1로 갈 땐 이동시간이 필요없는 것이다.

마지막으로 입력받은 값도 위와 같이 값을 더해주면 된다.

코드

---

import sys

N = int(input())
A, B = [[0] * (N+1) for _ in range(2)]
movetime = [[0, 0] for _ in range(N+1)]

for i in range(1, N):
    if i <= N:
        a, b, a2b, b2a = map(int, sys.stdin.readline().split())
        movetime[i] = [a2b, b2a]

        # Ai로 올 수 있는 경우는 Bi-1 -> Ai, Ai-1 -> Ai
        total_a2a = A[i-1] + a
        total_b2a = B[i-1] + movetime[i-1][1] + a
        A[i] = min(total_a2a, total_b2a)

        # Bi로 올 수 있는 경우는 Ai-1 -> Bi, Bi-1 -> Bi
        total_b2b = B[i-1] + b
        total_a2b = A[i-1] + movetime[i-1][0] + b
        B[i] = min(total_b2b, total_a2b)

a, b = map(int, sys.stdin.readline().split())
 # Ai로 올 수 있는 경우는 Bi-1 -> Ai, Ai-1 -> Ai
total_a2a = A[N-1] + a
total_b2a = B[N-1] + movetime[N-1][1] + a
A[N] = min(total_a2a, total_b2a)

# Bi로 올 수 있는 경우는 Ai-1 -> Bi, Bi-1 -> Bi
total_b2b = B[N-1] + b
total_a2b = A[N-1] + movetime[N-1][0] + b
B[N] = min(total_b2b, total_a2b)

print(min(A[N], B[N]))
    

결과

---