BOJ 1006 - 습격자 초라기

문제 :
https://www.acmicpc.net/problem/1006

DP[i][j] : i 번째 열, j타입일 때 남은 열을 적절히 놓아서 만들 수 있는 최소 침투 소대수라고 정의하고 다이나믹 프로그래밍으로 풀면 된다.

이 문제에서 까다로운 점은 구역이 원형으로 연결돼 있다는 점인데, 이는 처음과 끝에 이미 몇개의 소대를 보내 놨다고 생각 (이러면 선형구조로 생각할 수 있음) 하고, 그 경우에 대해 모두 돌려보면 된다. 길이 N에 처음과 끝을 가정하는 경우의 수는 상수번 이므로 O(N)에 풀린다.

코드 :
http://ideone.com/XPpr2X

비슷한 문제 (이 문제를 푸는데 동원된 아이디어와 비슷한) :
https://www.acmicpc.net/problem/9465
https://www.acmicpc.net/problem/2133
https://www.acmicpc.net/problem/2482
https://www.acmicpc.net/problem/4017