bit 연산 : on/off 상태가 20개 언저리면 고려해 보자

 구현 카데고리 7번째 글입니다. 오늘은 상태를 어떻게 나타내는지에 대한 이야기를 해 보도록 하겠습니다. 켜졌다와 꺼졌다. 이것은 각각 1과 0으로 표현이 가능합니다. 울타리가 있다. 울타리가 없다. 또한 1과 0으로 표현이 가능합니다. 즉, 어떠한 상태가 2개만 있을 때, 우리는 bit operation을 이용할 수 있습니다. 이걸 어떻게 써야 할까요?

 

 

---

 예제를 다소 어려운 문제로 잡아보겠습니다. 백준 1200번, BOI 2008 #5번 문제인 기상 예측 문제를 봅시다. 이 문제는 가로선 n개와 세로선 m개로 영역을 적절히 나눌 때, 부분합의 최대를 최소로 하는 문제입니다. 예를 들어, 2 by 3짜리 영역에, 가로선 1개, 세로선 1개를 그을 수 있다고 해 봅시다.

 

 

 그러면 이렇게 그을 수 있습니다. 이 때, 나눠진 영역의 부분합은 각각 5, 5, 5, 3입니다. 이 중 최댓값은 5임을 알 수 있어요. 아래와 같이 나누면 어떨까요?

 

 

 이 때에는 부분합이 각각 2, 8, 2, 6입니다. 최댓값이 8입니다. 이 두 경우 중 부분합의 최대가 최소인 경우는 5입니다. 따라서 답은 5가 됩니다. 그러면 이 문제를 어떻게 해결해야 할까요? 여기서 관찰할 수 있는 사실은 이러한 경우에, invaild 하다는 것입니다.

 

 

 가로 선이 삐툴어 졌기 때문입니다. 0번째 열과 1번째 열 사이에 세로선을 그었다면, 격자판을 완전히 나눠야 합니다. 그런데 그렇지 않았습니다. 따라서, 격자를 통과하는 세로선은 선택 되었다면, 그 세로선을 기준으로 격자가 나뉠 겁니다. 그렇지 않다면 나뉘지 않을 겁니다.

 

 

---

 이 사실을 간파했다면, bit 연산자로 어떻게 비빌 수 있다는 것을 알 수 있습니다. 격자의 행과 열 갯수는 18개 이하이므로, 그을 수 있는 세로선과 가로선은 17개 이하입니다.

 

 

 그러면, 여기서 bit를 어떻게 적용할 건지 생각해 봅시다.

 

 

 가로 선은 생각하지 말고, 세로 선 먼저 생각해 봅시다. s1만 택했다고 해 봅시다. 그러면 초록색 부분과 하늘색 부분으로만 나뉩니다. 이것은 1번만 선택했으므로 상태 1로 표현할 수 있습니다.

 

 

 2번만 선택한 경우는 어떤가요? 역시 초록색과 하늘색으로 나뉩니다. 그리고 이 때 상태는 2로 표현할 수 있습니다.

 

 

 1번과 2번을 다 택한 경우에는 초록색, 노란색, 하늘색 영역으로 나눌 수 있습니다. 이 때 상태는 3으로 표현할 수 있어요. s1이 켜졌는지 꺼졌는지를 0번째 bit로, s2가 선택되었는지 선택되지 않았는지를 1번째 bit로 본다면, (1<<0) + (1<<1) = 3으로 표현이 가능합니다.

 

 

 그러면, 이런 경우는 어떻게 표현이 가능할까요? 1번째, 3번째 선분으로 인해서 나누어 졌기 때문에 1 + 4 = 5로 표현할 수 있습니다.

 

 

---

 가로선을 그었습니다. 이 가로선을 기점으로 상태가 달라질 수 있을까요? 그럴 수는 없습니다.

 

 

 만약에 그렇다면, 일치하지 않는 상태가 최소 하나 이상 있다는 겁니다. 그런데, 제가 상태를 무엇이라 정의했나요? i번째 가로선이 그어졌는가? 그렇지 않은가? 였어요. 격자를 세로선이 관통한다면, 가로선을 기준으로 이전도 관통하고 있는 상태고, 이후도 관통하고 있는 상태입니다. 만약에 관통하지 않는다면, 가로선을 기준으로 그 선분은 그어져 있지 않을 거에요.

 

 

 즉, 빨간 선분을 기준으로 보면, 빨간 선 전에도, s1과 s3은 그어져 있어요. 빨간선 아래에도 그어져 있어요. s1과 s3은. 그런데 s2는 그어져 있나요? 굵게 그어져 있지 않아요. 빨간선 위쪽과 아래쪽의 상태가 같다고 봐도 되나요? 직관적으로 세로 선을 먼저 그을지 말지 선택하고, 가로선을 그어본다고 생각하면 편합니다.

 

 여기서 하나만 더 생각해 봅시다. 세로 선을 그을 수 있는 경우가 최대 2^17가지가 나올까요? 아닙니다. 세로선을 k개 긋겠다는 명확한 조건이 있기 때문입니다.

 

 

 n이 상수고, k가 변수일 때, nCk의 최댓값은 nC[n/2]입니다. n이 17이라면 17C8이 최댓값이 되는데요. 이 값은 24310입니다. 2^17이 131072라는 것을 생각해 보면, 단 1/5 ~ 1/6정도밖에 되지 않아요. 따라서, 세로선을 k개 그었다면, 켜진 bit가 k개인 상태만 고려하면 됩니다. 이를 vector u에 넣음을 알 수 있어요.

 

 

 _count 함수는 그렇게 어렵지 않게 구현할 수 있습니다. 다음에 가로 선 위와, 아래의 상태가 같아야 합니다. 다를 수는 없습니다. 무조건 세로선을 그으면, 격자를 관통하기 때문입니다. 이 포인트만 잘 잡으면, 구현 문제로 convert 할 수 있습니다.

 

 

 여기서 dp[i][xx][j]는, xx번 row까지 보았을 때, 선분을 i개 썼고, 세로 선을 긋고 안 긋고의 상태가 u[j]라는 의미입니다. 이 for loop를 유심히 보셨다면 눈치를 채셨겠지만, dp[i][xx][j]를 업데이트 하는데, 단지, dp[??][??][j] 값만 쓴다는 것을 알 수 있어요. dp[??][??][j-1]을 쓰지는 않는다는 것을 알 수 있어요.

 

 세로선을 그은 상태를 BIT로 표현을 하고, 2개의 factor, {tt, xx}를 잡습니다. 즉 가로선을 xx번 row까지 보았을 때, tt개를 그었다. 관통한다는 것을 어떻게 표현할까에 대한 것만 잘 잡는다면, 그냥 약간의 dp를 섞은 구현 문제로 convert가 될 수 있다는 것을 알 수 있어요. 이 글의 내용을 한 줄로 요약하면 아래와 같습니다. bit operation을 이용한 기법은 보통 이럴 때 씁니다.

 

 1200번은 On/Off로 나타낼 수 있는 상태가 무엇이였나요? 세로 선이 있고 없고. 그것이 최대 몇 개였나요? 17개. 그렇기 때문에 Bit를 고려해 볼 수 있었던 것입니다.