boj 16153 비트와 가희

https://www.acmicpc.net/problem/16153

16153번: 비트와 가희

1 이상 B 이하의 정수 중 특정 bit가 set되어있는 A의 배수는 몇 개인지 구하는 문제이다.

---

Meet In the Middle과 간단한 누적합 DP를 이용하여 구할 수 있다.

B / A가 5천만 이상일 경우, A의 모든 배수를 for문을 돌며 확인하면 시간 내에 통과 가능하다.

A가 특정숫자(128로 가정) 이상인 경우 A의 모든 배수를 for문을 돌며 조건을 만족하는 숫자를 구하고,

A가 특정숫자(128)이하인 경우 meet in the middle + dp를 적용하여 문제를 해결하였다.

 

[누적합 DP 배열]

 

DP 배열을 선언한다.

DP[128][1<<16]

 

DP[i][j]는 다음과 같이 정의한다. 

- DP[i][j] : 0~j까지의 숫자 중, A로 나누었을 때의 나머지가 i이며, 주어진 bit가 모두 set되어있는 숫자의 개수.

- ex) set되어야하는 bit가 1, A가 3이라면 DP[2][8] = 2 (2, 5가 해당 조건을 만족한다.)

 

이와같은 DP배열은 128 * 65536번의 loop로 생성 가능하다.

 

[meet in the middle]

위에서 누적합 DP배열을 생성하면서 meet in the middle의 한쪽방향을 완성했으므로, 다른쪽 방향도 완성해보자.

직전에 0~15번 bit까지를 다루었으므로, 이번엔 16~30번째 bit까지 다뤄보자.

 

x를 set되어야하는 상위 15개 bit가 모두 set되었으며, 하위 16bit가 모두 0인 숫자라고 할 때,

DP[ (A - (x % A)) % A ][65535]가 상위 15bit가 x로 고정일 떄, 하위 16bit도 조건을 만족하는 숫자의 개수이다.

x를 1<<16씩 더해가며 결과값을 누적하면 답을 도출할 수 있다.

마지막으로, x가 B의 상위 15bit와 일치하는 경우, DP[ (A - (x % A)) % A ][B의 하위 Bit]를 더해줘야 한다.

 

설명에서는 총 31bit를 상위 16bit, 하위 15bit로 나누고, 128미만인 A에 대해서만 meet in the middle을 고려하였지만,

16, 15, 128과 같은 상수를 수정하면 좀더 좋은 시간복잡도로 답을 구할 수 있다.