그동안 여러 일들이 있어서 포스팅을 잠시 쉬었더니, 흐름을 놓친것 같습니다. 평소에 풀만한 문제를 아예 접근하지 못해서, 조금은 뒤로 물러나서, 웜업하는 의미로 기초적인 문제를 소개할까 합니다.
Problem
이번 문제도 이해하기엔 전혀 어렵지 않습니다. 한 숫자열이 주어지고, 그 열의 부분합을 반환하는 아주 간단한 문제입니다. 함정이 하나 있다고 하면, 제한시간이 0.5초여서, 부분합을 그 자리에서 만드는, brute-force 방식으론 시간복잡도를 만족하기 어렵습니다. 따라서 다른 방법이 필요합니다.
Approach & Solution
저도 처음엔 brute-force 방식의 접근을 시도했지만, 시간초과가 뜬것을 보고 잘못 풀었구나 알았습니다ㅎㅎ
그래서 Memoization을 활용하여, n자리의 구간합을 미리 만들어 놓으면 어떨까 싶어서 그렇게 접근해 보았습니다.
만약, 3-5까지의 구간합을 원한다면, 5까지의 구간합에서, 2까지의 구간합을 빼면 기존보다는 빠를테니까요.
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
target = list(map(int, input().split()))
sum_target = [0]
for i in range(n):
sum_target.append(sum_target[-1] + target[i])
answer = []
for _ in range(m):
start, end = map(int, input().split())
temp = sum_target[end] - sum_target[start-1]
answer.append(temp)
print('\n'.join(map(str, answer)))열받게도, 그 방식도 시간초과가 나긴 했습니다. 그래서 혹시 몰라 input = sys.stdin.readline을 사용하여 입력을 더 빨리 받아보니 통과가 되더군요.
Conclusion
앞으로 알고리즘 포스팅을 좀 빡세게 할 생각입니다. 지금까지는 정말 최소한의 양만 했다면, 앞으로는 조금더 체계적으로 알고리즘별로, 난이도 별로 접근하면서 포스팅할 생각입니다. 그 시작으로 가장 기초이면서, 결국 가장 중요한 자료구조인 배열 문제를 풀어보았습니다!
SailingToTheMoooon