백준 3673번 :: 나눌 수 있는 부분 수열 - C++
힌트 1. i번째부터 j번째까지 연속하는 부분수열의 합을 \(A_{i, j}\)라고 하면, \[A_{i, j} = A_{1, j} - A_{1, i}\] 이므로 '연속하는 부분 수열의 합'을 '두 개의 부분 수열 누적합의 차'로 표현할 수 있다. 2. 1번의 내용을 응용하면, \[A_{i, j} \, mod \, d = (A_{1, j} - A_{1, i}) \, mod \, d = 0\] 이고, 이는 곧 \[A_{1, j} \, mod \, d = A_{1, i} \, mod \, d\] 이므로 '연속하는 부분 수열의 합이 d로 나누어 떨어지는 것'은 '두 부분 수열 누적합을 d로 나눴을 때의 나머지가 동일한 경우'와 같다. 3. 추가로 부분 수열 누적합의 나머지가 0인 경우 해당 부분 수열은 독자적으..
2023. 8. 7.
