221027 문제 풀이 기록

P3 | 5962 - Generic Cow Protests

풀이 시간: 55분

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

prefix sum을 만들었을 때, 각 prefix sum 값에 대해 sum[i] <= sum[j]인 모든 i에 대해 DP[j] += DP[i]를 해주자. segtree를 사용하여 이를 최적화할 수 있다.

여담: 원래 f(x, y) = (x부터 y까지 그룹의 합이 0 이상이면 1, 아니면 0) 이라고 할 때 DP[i] = DP[1]*f(2, i) + DP[2]*f(3, i) + ... 방식의 dp를 생각했었는데, 거기서 35분 박고 나서야 다른 방식을 생각하기 시작했다.

자력으로 P3 수준 문제를 풀 수 있게 되었다는 점이 새삼 뿌듯하다. 몇달 전까지만 해도 플레티넘은 쳐다도 못봤었는데...