[BOJ] 10846번: Bali Sculptures

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

A = 1일 경우에는 1부터 i번째 조각상까지를 target에만 있는 bit로 나누기 위해 필요한 최소 그룹의 수를 D[i]라고 할 때 D[N] <= B인지 확인하면 그 target이 valid한지 알 수 있습니다. O(N^2*40)에 해결할 수 있습니다.저는 872ms가 걸리는데 완벽히 동일한 방법으로 짠 다른 사람의 코드가 100ms 안쪽인 것을 보고 Cache hit rate 때문에 생긴 문제인지 다른 제가 놓친 점이 있는지 조금 의문이 들었습니다.

A != 1일 경우에는 http://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/422 D번 문항을 참고하면 되겠습니다.

https://github.com/blisstoner/BOJ/blob/master/10846.cpp