백준 BAEKJOON 32193번 승강장의 깊이 [PYTHON/파이썬]

 

 

 

 

 

백준 BAEKJOON 32193번 승강장의 깊이 [PYTHON/파이썬]

---

<문제 출처> (BRONZE Ⅲ)

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

 

 

 

 

 

 

 

 

 

<풀이>

처음 풀었을 때는 시간 초과가 떠서 당황했다.

단순하게 생각했던 게 잘못이었던 것 같았다.

# 처음 풀이 (시간 초과)
N = int(input())
tmp = 0

for _ in range(N):
    A, B = map(int, input().split())
    result = A - B + tmp
    print(result)
    tmp = result

 

 

 

고민하던 찰나에 누적합을 적용하니 정답처리가 되어서 문제를 풀 수 있었다.

누적합에 관한 내용은 아래의 글을 참고하면 좋다!

백준 BAEKJOON 11441번 합 구하기 [PYTHON/파이썬]

 

 

 

 

 

 

 

<코드>

import sys
input = sys.stdin.readline

N = int(input())
platform = [0]  # 원본 배열
S = [0] * (N + 1)  # 누적합 배열

# 원본 배열 작업
for _ in range(N):
    A, B = map(int, input().split())
    platform.append(A - B)

# 누적합 배열 작업
for k in range(1, N + 1):
    S[k] = S[k - 1] + platform[k]

# 출력
for i in S[1:]:
    print(i)