https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
본 문제는 제목에서 말하듯이 구간합 이라는 알고리즘을 이용해야한다.
특정 숫자가 [5, 4, 3, 2, 1]이 들어왔을 때, 각 요소별로 구간합을 미리 구해놓는다.
즉, [5, 5 + 4, 5 + 4 + 3, 5 + 4 + 3 + 2, 5 + 4 + 3 + 2 + 1] => [5, 9, 12, 14, 15]가 나오게 된다.
이후, 특정 구간의 합을 구하라고 하면, 그 구간만큼 빼서 구간합을 구할 수 있다.
본 문제는 위와 동일한 문제이다.
num에 리스트를 받아오고, for문을 통해 위와 같은 요소별 구간합을 구했다.
이후, i, j에 따라 구간합을 구하는 문제였다.
but, i가 1인 경우에는 처음 요소부터 j번째 요소까지 합을 의미하는것이므로 if i == 1일 경우 j번째 요소만 출력하게 하였다.
그리고 또다른 조건으로는 5번째 요소에서 5번째 요소까지의 합을 구할때는 해당 5번째 요소만 구하면 되는 것이다.
즉, 5번째 요소 - 4번째 요소를 통해 오직 5번째 요소만 출력하게끔 하였다.
이러한 예외사항 빼고는 구간합 알고리즘처럼 구간만큼 빼서 답을 구했다.
'백준에 대가리 깨지는중' 카테고리의 다른 글
| [백준] 실버1 쉬운 최단거리 (0) | 2023.06.05 |
|---|---|
| [백준] 실버3 조합 (0) | 2023.06.05 |
| [백준] 실버1 단지번호붙이기 (0) | 2023.06.01 |
| [백준] 실버1 쿼드트리 (0) | 2023.05.30 |
| [백준] 골드4 이중 우선순위 큐 (2) | 2023.05.30 |