백준 1006 습격자 초라기 깔끔하게 다시 풀기

[ngja]

Link

문제 풀이

3가지 케이스의 dp 값 사용

1. i 번째 왼쪽이 직선으로 끝나는 경우
2. i 번째 위 칸만 채워진 채로 끝나는 경우
3. i 번째 아래 칸만 채워진 채로 끝나는 경우

순서대로 값을 점화식 대로 채워 나가는데 4가지 케이스가 있다.

1. 기본 상태 그대로 직사각형 모양
2. 왼쪽 위, 오른쪽 위만 하나로 합쳐진 ㅗ 모양
3. 왼쪽 아래, 오른쪽 아래만 하나로 합쳐진 ㅜ 모양
4. 왼쪽 오른쪽 둘 다 합쳐진 작아진 직사각형 모양

4가지 모든 케이스에서 가장 적게 블록을 사용한 케이스가 정답