누적합

[Java/백준] 구간 합 구하기 #11659

문제 풀이 (1) 문제 분석하기 수의 개수 N과 합을 구해야 하는 횟수 M은 최대 100,000 임 최악의 경우, 1억 회 이상 연산을 해야 하므로 1초 안에 계산을 끝낼 수 없음 → 구간 합 사용! (2) 손으로 풀어보기 // 합 배열 공식 S[i] = S[i-1] + A[i] // 구간 합 공식 S[j] - S[i-1] N개의 수를 입력받으면서 바로 합 배열 생성 i부터 j까지 구간 합 공식으로 정답 출력 배열의 index는 0부터, 합 배열의 index는 1부터 시작한다는 것에 주의하기! (3) 슈도코드 작성하기 N(숫자의 개수), M(질의 개수) 저장하기 for(1부터 N 까지) { 합 배열 생성하기(S[i] = S[i - 1] + A[i] } for(0부터 M 전까지) { 질의 범위 받기(i ~..