<div id="readability-page-1" class="page"><div>문제 및 채점: <a href="https://oj.uz/problem/view/IOI20_biscuits" target="_blank" rel="noopener">oj.uz</a>

$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$는 가장 큰 수의 비트 수다.

</div></div>

PS 이야기

문제 및 채점: 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$는 가장 큰 수의 비트 수다.
 
더보기
#include 
#include "biscuits.h"
using namespace std;
typedef long long lld;
lld count_tastiness(lld x, vector a)
{
	vector status(63, 0);
	lld sum = 0;
	for (int i=0;i>j){
				cur -= x<

IOI2020 Day2 biscuits 풀이

댓글