https://www.acmicpc.net/problem/11659
Falied
# DP : O(N + M)
import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
arr = [0] + list(map(int, input().rstrip().split()))
# DP 테이블 초기화
dp = [0] * (N+1) # 1~N번째 원소 저장
for i in range(1, N+1):
dp[i] = dp[i-1] + arr[i] # 첫번째 원소부터 i번째 원소까지의 누적합
# 누적합 구하기
for _ in range(M):
L, R = map(int, input().rstrip().split())
#print(dp, R, ':', dp[R], L-1, ':', dp[L-1], dp[R] - dp[L-1])
print(dp[R] - dp[L-1])
분명 누적합을 구하는 부분에서 있어서 DP를 사용해야 하는 문제라고 생각했지만,
base case와 점화식을 못세우겠어서 다짜고짜 완전탐색으로 풀었다.
그 결과 채점 40%만에 시간초과
가 났다.
# 완탐 : O(MN) -> O(10^10)
import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
arr = [0] + list(map(int, input().rstrip().split()))
task = [list(map(int, input().rstrip().split())) for _ in range(M)]
memo = {i:arr[i] for i in range(len(arr))}
for i in range(len(task)):
print(sum(arr[task[i][0]:task[i][1]+1]))
시간복잡도 계산해보고 DP로 풀어야한다고 생각되는 문제는 꼭 관계 찾기