BOJ 11659 구간 합 구하기 4

태그

누적 합

URL

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

문제 설명

•

수 NNN개가 주어졌을 때, iii번째 수부터 jjj번째 수까지 합을 구하는 프로그램을 작성하는 문제

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

1≤N≤100,0001 ≤ N ≤ 100,0001≤N≤100,000

•

1≤M≤100,0001 ≤ M ≤ 100,0001≤M≤100,000

•

1≤i≤j≤N1 ≤ i ≤ j ≤ N1≤i≤j≤N

문제 풀이

풀이1 브루트 포스 - O(N⋅M)O(N \cdot M)O(N⋅M)

풀이2 그리디

풀이3 DP - O(N)O(N)O(N)

풀이 코드

import sys
input = lambda: sys.stdin.readline()

N, M = map(int, input().split())
num_list = [0] + list(map(int, input().split()))

# Solve (DP)
dp = [0 for _ in range(N + 1)]

for i in range(1, N + 1):
	dp[i] = dp[i - 1] + num_list[i]

for _ in range(M):
	i, j = map(int, input().split())
	print(dp[j] - dp[i - 1])
Python
복사