누적합
-
[백준] 2900번: 프로그램 - C++개발/알고리즘 & PS 2024. 8. 27. 01:23
https://www.acmicpc.net/problem/2900 문제 구현을 그대로 구현하면 답을 얻을 수 있다. 하지만 시간복잡도가 굉장히 커지기 때문에 시간 초과를 받게 된다. something 함수를 호출 하는 과정에서 $O(KN)$, 합을 구하는 과정에서 $O(QN)$의 시간복잡도가 필요하다. 하지만 $N, K, Q$가 최대 $10^6$까지 커질 수 있으니 시간 제한을 만족시킬 수 없다.구간 합구간의 합은 누적합을 사용하면 $O(1)$에 구할 수 있다. 따라서 누적합을 적용하면 $O(Q)$에 처리가 가능하다. something 호출매번 입력이 주어질 때마다 갱신하면 연산을 여러 번 반복하게 된다. 예를 들어 첫번째 원소는 항상 1씩 증가한다. 따라서 매번 업데이트 하지 말고 각 입력이 주어진 횟..
-
[BOJ] 2143 두 배열의 합 - C++개발/알고리즘 & PS 2024. 4. 4. 11:28
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그www.acmicpc.net아이디어두 수열 $A_n$, $B_m$의 연속한 원소들의 합을 $T$가 되도록 만들면 된다. 누적합을 통해 연속한 원소의 합을 빠르게 구할 수 있고 이분탐색을 통해 가능한 경우의 수를 빠르게 셀 수 있다. 부분합은 $1$부터 $i$까지의 합이고 이번 문제에서는 $i$부터 $j$까지의 합이 필요하므로 미리 나올 수 있는 모든..