티스토리 뷰

IOI/IOI2020

IOI2020 Day2 biscuits 풀이

전명우 2020. 9. 23. 23:56

문제 및 채점: oj.uz

 

$K$ 개 종류의 비스킷이 있고, 각 종류는 번호가 1부터 $K$까지 매겨져 있다. $i$번 종류의 비스킷의 맛 점수는 $2^{i-1}$이며, $i$번 종류의 비스킷은 $a[i]$ 개 있다. 비스킷 일부를 선택하여 비스킷 바구니 $x$ 개에 나눠 담을 건데, 각 비스킷 바구니에 담긴 비스킷 맛 점수의 합을 동일하게 해야 한다. 이렇게 나눌 때 만들 수 있는 바구니에 담긴 비스킷 맛 점수의 합의 수를 구하는 문제다.

 

다음과 같은 DP 배열을 정의하자.

$$D[i] = \text{1번부터 }i\text{번 비스킷까지 사용했을 때 만들 수 있는 합의 수}$$

초기값은 $D[0] = 1$이 된다.

 

$i$ 번 비스킷까지 사용하여 만들 수 있는 합 중 가장 큰 수를 $b$라고 하자. 그러면 아래 점화식으로 $D[i]$를 계산할 수 있다.

$$D[i] = \biggl(\sum{D[j]}\biggr) + 1\ \bigl(b\text{의 }j\text{ 비트가 1인 모든 }j\text{에 대해}\bigr)$$

예를 들어, $i = 8$이고, $b = 41 = 101001_{(2)}$인 경우에 대해 $D[i]$ 값 계산 점화식이 어떻게 동작하는지 확인해보자. $b$의 비트 중 1인 비트는 0비트, 3비트, 5비트다. 점화식에 따르면 $D[8] = D[0]+D[3]+D[5]+1$가 된다.

* $D[5]$는 만들 수 있는 합 중 이진수로 표현했을 때 $000?????_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

* $D[3]$은 만들 수 있는 합 중 이진수로 표현했을 때 $00100???_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

* $D[0]$은 만들 수 있는 합 중 이진수로 표현했을 때 $00101000_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

* 마지막으로 $1$은 만들 수 있는 합 중 이진수로 표현했을 때 $00101001_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

 

만약, 만들 수 있는 가장 큰 수 $b$가 0인 경우 바구니에 수가 들어 있지 않은 경우만 가능하므로 $D[i] = 1$이 되어, 위 점화식이 이 경우에도 유효하다. 이렇게 DP를 계산하면 시간복잡도 $O(B^2)$이 된다. 여기서, $B$는 가장 큰 수의 비트 수다.

 

더보기

'IOI > IOI2020' 카테고리의 다른 글

IOI2020 Day2 mushrooms 풀이  (0) 2020.09.24
IOI2020 Day2 biscuits 풀이  (0) 2020.09.23
IOI2020 Day2 stations 풀이  (0) 2020.09.23
IOI2020 Day1 plants 풀이  (0) 2020.09.22
IOI2020 Day1 tickets 풀이  (0) 2020.09.22
IOI2020 Day1 supertrees 풀이  (0) 2020.09.22
댓글
댓글쓰기 폼