dh_0e

조합론이 기본이 되는 문제로 계산식 발상에 좀 애먹은 문제결론적으로 메뉴들을 맵기 순으로 정렬하면, 메뉴마다 가장 높은 수치, 낮은 수치일 경우의 수가 정해져 있으므로 각각의 메뉴마다 경우의 수를 조합론으로 구해 계산해주면 된다. 풀이과정한 메뉴가 포함되는 조합의 수는 총 $2^{n-1}-1$가지이다.하지만 스코빌 수치가 이용되는 경우만 따지면 되기 때문에 i번째 메뉴가 가장 높은 스코빌 수치일 때와 가장 낮을 때만 구해주면 된다. 식으로 나타내면 다음과 같다. (i가 0~n-1일 때)가장 높은 스코빌 수치일 경우 >> $2^i-1$가장 낮은 스코빌 수치일 경우 >> $2^{n-i-1}-1$i번째 메뉴보다 높거나 낮은 스코빌을 선택할 때 모두 선택하지 않은 경우의 수가 있기 때문에 -1을 해줌 $2^n$..

비트마스킹을 활용한 dp 문제, 근데 이제 큰 수 % k를 곁들인 .. 시행 착오 vector > dp[][]로 선언을 하여 dp[i][j] = i개의 원소를 합쳤을 때, 마지막 원소에 j번째 원소를 삽입한 pair(first = 지금까지 삽입한 원소들의 비트마스킹, second = k로 나눈 나머지)를 삽입하는 것으로 점화식을 짰다.이 후에 말도 안 되는 메모리 초과를 보여주며 전처리 및 메모리도 줄인 후 진행했는데 여전히 답이 안 보였다. 해결 방안갈아엎었다. 점화식부터 다시 구상하니 dp[i][j] = 지금까지 사용한 원소를 마스킹한 값이 i, 나머지가 j인 수열의 갯수 로 풀 수 있었다.전처리 및 dp에 각각 하나씩 사용한 경우의 수 저장ten_mod에 10^l 들을 k로 나눈 나머지를 모두 구해..