BOJ 4215 비밀 프로젝트

먼저 M의 개수를 고정합니다. $m = 1$일 경우에는 M을 하는 것이 아무 의미가 없으므로 M의 개수는 0만 고려하면 되고, 그 외의 경우에는 0 이상 30 이하의 M을 모두 체크해야 합니다.

가능한 최대 M만을 체크하거나 특정 M의 개수에서 방법이 없으면 더 이상 큰 M을 시도하지 않는 풀이를 생각하기 쉬운데, 이는 각각 다음과 같은 반례가 있습니다.

5 2 1 2 2 4 // M이 0개이면 답이 없으나, M이 1개이면 답이 있음
4 2 1 2 2 8 // 1A와 1M 모두 가능하며, M이 0개인 1A가 사전 순으로 최소임

M의 개수 $k$를 고정했다면, $p$와 $q$는 각각 $m^k p$와 $m^k q$가 되고, 임의의 위치에 A를 추가하게 되면 그 A 뒤에 오는 M의 개수 $j$에 대해 양끝에 $a m^j$가 더해집니다. 이는 모두 $a$의 배수이므로, 일단 맨 뒤에 A를 필요한 만큼 추가한 뒤, MA{m} -> AM의 변환을 하여 길이를 최소화하는 것을 생각할 수 있습니다. 맨 끝에 놓아야 하는 A의 개수는 $m^k p + a x \ge r$인 최소 $x$가 되며, 변환의 결과는 여기서 얻은 $x$값을 고정 길이의 $m$진법(첫 자리의 값은 무제한)으로 나타낸 것과 같습니다. 여기서 $m^k q + a x > s$이면 현재 M의 개수에 대해서는 답이 없는 것입니다.

그런데 여기에도 함정이 있습니다. 예를 들어 1의 자리에 $i$개가 있을 때, $m-i$개의 A를 추가로 더한 뒤 받아올림을 한 번 더 해주면 더 짧거나 사전 순으로 더 이른 답이 나옵니다. 따라서, 이러한 조정을 했을 때 여전히 범위에 들어오는지를 확인하여 가능하면 추가 조정을 해 주어야 합니다.