https://www.acmicpc.net/problem/11570
- 아름답게 풀려서 기분좋은 DP 문제
- DP Index의 기준을 매번 갱신해주는 문제이다.
- 단순하게 생각하면 3가지 상태가 필요하다.
- X: 지금까지본 Index
- LA: A 집합에 속한 마지막 Index
- LB: B 집합에 속한 마지막 Index
- 조금만 생각해보면 X는 LA나 LB 둘중 하나와 같다. 즉 아래 두개로 줄일수 있다.
- X: 지금까지 본 Index
- Lother: X를 포함하는 집합이 아닌 집합의 마지막 Index
1 |
|