https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 주어진 배열의 구간 합이 m으로 나누어떨어지는 경우의 수를 구하는 문제 제출하고 다른 사람들의 풀이를 보니 다들 조합으로 풀어서 신기했던 문제이다. 조합으로 푸는 방법은 생각지도 못했는데, 다른 사람들의 풀이를 보니 조합으로 접근했어도 괜찮았을 듯 싶다. 우선 배열 i ~ j의 누적 합을 구해주는데, 어차피 나머지가 중요하므로 나머지의 누적 합을 구..
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]까지 가기 위해 남은 시간을 저..
