[BOJ] 11441

less than 1 minute read

합 구하기

11441번 https://www.acmicpc.net/problem/11441

구간의 합을 구할때마다 선형으로 답을 구한다면 O(NM)으로 시간초과가 날 수 있습니다.
acc[i]에 1번째숫자부터 i번째 숫자까지의 합을 저장한다면,
ANSi, j = acc[j] - acc[i - 1]; 로 O(M)만에 해결할 수 있습니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/11441.cpp

Categories:

Updated:

Leave a comment