AtCoder Beginner Contest 249 F - Ignore Operations

 

F - Ignore Operations

dp [i][j] : i개까지 문자를 봤을 때 변환되는 문자의 길이를 j라고 할 때의 경우의 수

라고 놓고 문제를풀면 잘 풀리지만 최적화를 해야 풀린다. 그냥 dp 채우면 O(N^3)이다.

 

1.

1차원 또는 2차원 또는 3차원 dp 상관없이 dp를 바텀업으로 채울 때

중간에 어떤 연속적인 값을 더하는 구간이 존재한다면

dp를 채우면서 prefix_sum을 이용하면 연속적인 숫자의 방향의 개수에 따라 그 개수만큼 시간 복잡도의 차수를 줄일 수 있다.

dp를 해석하기보다 수치적으로 저런 구간이 나오면 그냥 prefix sum을 이용해서 압축시키면 된다.

먼저 문제에 대한 dp를 작성을 하고, 수치적으로 최적화하면 된다.

 

2.

mod 연산의 prefix sum을 이용할 때 주의해야 할 점이 음수가 나올 수 있다는 것이다. (굉장히 중요)

정말 중요하다. mod 연산에서의 뺄셈은 주의하자.