BOJ 16679 - Back to the Bones
완전히 잘못 접근해서 꼬인 문제이다.
정해는 다음과 같다.
항상 주사위들 중, $a_i > a_j$ 라면 $j$ 번째 주사위를 돌리는 것이 최적이다.
따라서 오름차순으로 정렬햇을 때 prefix만 돌려야하는 주사위가 된다.
$dp[i][k]=$ $i$ 개의 주사위를 돌렸을 때 총 합이 $k$가 나오는 경우의 수 라고 두고
$dp[0][0]=0, ~ dp[i][k]=\displaystyle \sum_{d=1}^{6}dp[i-1][k-d]$ 가 된다.
이제 $0 \sim N$개의 주사위를 돌리고 그 뒤는 가만히 냅두는 모든 경우를 검사한다.
$x$ 개의 주사위를 돌렸다면 나머지 $N-x$ 개의 주사위의 합이 $S$라 할 때, 우리가 구하려는 $6^N$을 곱한 값은 $f(x)= \displaystyle \sum_{s = \text{Max}(0, k-S)}^{6N} dp[x][s] \cdot \left(\dfrac{1}{6^x} \cdot 6^N\right)$
이고 가장 $f(x)$가 큰 $x$가 주사위를 몇개 돌릴지에 대한 정답이다.
작은것부터 $x$개를 채워주면 된다.
Comments