[JAVA / 자바] 백준 11659번 - 구간 합 구하기 4 (실버 3)
문제
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ i ≤ j ≤ N
출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
문제 접근 방법
이번 문제는 누적 합 문제인데 개인적으로 다이나믹 프로그래밍 문제와 같다고 생각한다.
누적 합을 저장할 배열을 n+1칸만큼 선언해주고, 1번 인덱스부터 n번 인덱스까지 [idx] =[idx-1] + 입력된 수 해주면서 수 입력을 저장하고, 이후 누적 합을 출력해주면 된다.
세 번째 줄부터 입력은 i번 수 ~ j번 수까지의 합이므로 이전에 구해놓았던 누적 합 배열에서 [j] - [i-1] 값을 출력해주면 된다.
JAVA 코드 풀이
코드 실행 결과
후기
이번 문제는 처음에 일일이 누적합을 구하려다가 시간 초과가 났다. 그도 그럴 것이 동일한 연산을 몇 번이고 반복하는데 문제를 낼 때 조건으로 제한을 걸어두지 않았다면 굳이 문제를 풀 이유가 없었을 엄청 단순한 문제였을 것이다. 이후 생각을 해 보다가 다이나믹 프로그래밍(Dynamic Programming) 알고리즘이 생각이 나서 점화식을 찾아 입력이 들어오는 대로 누적 합을 배열에 저장해가면서 풀어보았더니 문제가 해결되었다.
문제 원본
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net