https://www.acmicpc.net/problem/10986 풀면서 그렇게 어려운 문제는 아니었으나, 오랜만에 보니 잘 기억이 안나서 정리 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하라는 문제인데,보자마자 배열에 나머지만을 저장해도 되겠다는 생각이 들었다.또한, 연속된 구간의 개수이므로 누적합을 이용해야지 시간초과를 방지하지 않을까라는 생각도 들었다.12345678910111213141516171819#include iostream>using namespace std;int sum[1000001], cnt[1001];int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ..
Prefix Sum
https://www.acmicpc.net/problem/27651 27651번: 벌레컷 크기 $N$의 $1$차원 양의 정수 배열로 이루어진 자벌레가 있다. 자벌레는 곤충이기 때문에 머리, 가슴, 배로 부위를 구분할 수 있다. 각 부위는 배열상에서 연속하는 구간으로 나타낼 수 있으며 배 www.acmicpc.net 주어진 수열을 3분할하는데, 이를 각각 머리, 가슴, 배라고 지칭한다. 1 ~ x 의 크기 < y + 1 ~ n의 크기 < x + 1 ~ y 를 만족하는 수열의 개수를 구해야한다. 즉, 머리 < 배 < 가슴을 만족해야한다. 이를 위해 우선 1 ~ n까지의 수열의 합을 배열에 저장해주어 중복으로 덧셈을 실시하는 일이 발생하지 않도록 누적합을 이용했다. 먼저 1 ~ x를 구하는 것은 간단하다. 단..
https://www.acmicpc.net/problem/27728 27728번: 개구리와 쿼리 $N \times N$ 크기의 $2$차원 배열로 이루어진 연못에 $Q$마리의 개구리들이 모여있다. 각 개구리들은 초기 위치 $\left(S_{x},S_{y}\right)$에서 배열의 오른쪽 끝$\left(X,N+1\right)$에 있는 육지에 도착해야 한 www.acmicpc.net 문제는 누가봐도 dp + 누적 합으로 해결하는 문제이다. 나도 처음에는 간단하다고 생각했는데, 막상 머릿속으로 시간을 계산해보니까 x좌표 N개, y좌표 N개, 개구리 Q마리 ->O(N^2*Q)가 걸렸다. 이는 당연히 시간초과이고, 시간을 줄일 방법을 찾아야했다. 먼저 dp[i][j]에 dp[i][n]까지 가기 위해 남은 시간을 저..
