주어빈 배열의 i번째에서 j번째까지의 합을 구하는 문제이다.
더이상 따로 설명할 것없이 겉으로 보기에는 간단해보였는데 다 쓰고나니 시간초과에 걸렸다.
시간복잡도를 고려해야했다.
배열의 누적합을 구하는 경우, 배열을 모두 훑게되면 시간 복잡도가 O(N^2)으로 늘어난다.
따라서 prefix sum을 위한 배열을 하나 더 만들어주고, 거기에 누적 합을 따로 저장해둔다.
그리고 i,j가 제시되면 j번째에서 i-1번째 누적합을 빼면 된다.
끝!
'공부 > 백준' 카테고리의 다른 글
| [백준] 2108번 (0) | 2022.06.15 |
|---|---|
| [백준] 1010번 (0) | 2022.06.15 |
| [백준] 2331번 (0) | 2022.06.15 |
| [백준] 1316번 (0) | 2022.06.15 |
| [백준] 2577번 (0) | 2022.06.15 |
