[BOJ 1006] 습격자 초라기 "컷"

[BOJ 1006] 습격자 초라기 "컷"

2022. 11. 7. 22:52ㆍPS/Problem Solving

1006번: 습격자 초라기

하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소

www.acmicpc.net

dp: 시작 행의 상태, 끝 행의 상태를 기준으로 O(N*4*4) DP다.

재귀 dp를 한 1년만에 짜는 듯하다.

노가다 케이스워크 오랜만에 하니까 재밌었다.

나는 원형이기 때문에 양쪽 끝 4개씩 4*4=16개의 상태를 사용했는데 한쪽 4개만으로 가능하다.

곰곰히 생각해보면 그냥 0~N-1칸에 한 칸이 더 있다고 생각해서 0~N칸을 채우고 N칸이 상태 0(둘다 비어 있음)인 경우에 대해서만 고려하면 된다. 알아서 잘 구해준다. 끝

Pentagon