-
[백준] #11659 구간합 구하기4 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 16:22
문제
https://www.acmicpc.net/problem/11659
목표
N개가 주어졌을때 주어지는 구간의 합을 구하기
풀이
시간초과때문에 수를 읽을때마다 누적합을 구하는 배열을 생성함
그후 (n,m)범위가 들어오면 totalSum[m] - totalSum[n-1]연산으로 구간합을 구함
즉 (0~m) 까지의 전체합에서 (0~n-1)까지의 전체합을 빼주면됨
코드
#include <iostream> #include <vector> #define MAX 100001 using namespace std; int T, S; vector<int> vect; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> T >> S; vect.resize(T); int tmp; for (int i=1; i<=T; ++i) { cin >> tmp; vect[i] = vect[i-1] + tmp; } for (int j=0; j<S; ++j) { int tmp1, tmp2; cin >> tmp1 >> tmp2; cout << vect[tmp2] - vect[tmp1-1] << '\n'; } }
'Algorithm > 알고리즘 백준 풀이' 카테고리의 다른 글
[백준] #19115 가장 큰 정사각형 - (DP) (0) 2020.03.02 [백준] #9252 LCS2(Longest Common Subsequence) - (DP) (0) 2020.03.02 [백준] #2579 계단 오르기 - (DP) (0) 2020.03.02 [백준] #1932 정수삼각형 - (DP) (0) 2020.03.02 [백준] #1759 암호만들기 - (BF) (0) 2020.02.12