안녕하세요,
재재입니다.
BOJ 1852 수묶기 문제 풀이입니다.
BOJ 1852 수묶기
(1) 문제 설명
분류 : dynamic programming, bitwise operation
출처 : https://www.acmicpc.net/problem/1852
(2) 풀이 도출
bitwise operation 을 사용한 dyanmic programming 문제로 해결 할 수 있습니다.
조금 더 최적화된 방법을 사용하는 방법도 있지만 쉬운 방법을 설명드려볼게요.
상태공간은 다음과 같이 정의 할 수 있습니다.
dp[n][current][next] : n 번째 행을 채우는데,
현재 행의 상태는 current 고 다음 행의 상태는 next 일 때 최적값
여기서, 각 상태는 3 개의 bit 를 사용해서 표현 할 수 있습니다.
현재 상태를 S라고 가정해보겠습니다.
- S가 비어있는 상태라면, (000) -> 0
- 앞에 2개를 채운 상태라면, (110) -> 3
- 앞에 1개를 비우고 뒤에 2개를 채우면 , (011) -> 6
- 만약 여기에서 세로로 채우는 것을 고려한다면,
다음칸의 상태도 함께 사용 할 수 있습니다.
이제, 여기서 조금 더 개선한 방법이 있습니다.
공간복잡도를 조금 더 줄일 수 있는 상태공간을 정의하면 아래와 같습니다.
dp[n][S] : n 번째 행을 채우는 데 현재 상태가 S 일때, 최적값
이 방법의 핵심은 다음과 같습니다.
지금 지나온 칸은 고려하지 않아도 된다. 앞으로의 칸만 고려하면 되며,
지나온 칸에 남아있는 세로블럭만 고려하면 된다.
이제 이 방법은, bitwise shift operation 을 함께 활용하여 구현 할 수 있습니다.
(3) 정답 코드
BOJ 1852 수묶기