67

$m=6$과 $m=7$에 대해 각각 동적 계획법을 수행한다. $dp_m[r]$를 현재까지 본 문자에서 만들 수 있는, $m$으로 나눈 나머지가 $r$인 비어 있지 않은 부분수열의 최대 길이로 둔다. 만들 수 없다면 $0$으로 둔다.

다음 숫자 $d$를 볼 때는 그 문자를 버리거나, 길이 $1$인 새 수로 시작하거나, 기존 부분수열 뒤에 붙일 수 있다. 기존 나머지가 $r$이면 새 나머지는 $(10r+d)\bmod m$이다. 전이에는 문자를 보기 전의 상태만 사용한다.

모든 문자를 처리한 뒤 $L=\max(dp_6[0],dp_7[0])$을 구한다. $L=0$이면 $-1$을 출력하고, 그렇지 않으면 $N-L$을 출력한다. 한 케이스의 시간 복잡도는 $O(N)$이고, 문자열을 저장하는 공간을 제외한 추가 공간 복잡도는 $O(1)$이다.

증명

처음에는 비어 있지 않은 부분수열을 만들 수 없으므로 모든 상태가 $0$이다. 다음 문자를 처리할 때 가능한 부분수열은 그 문자를 쓰지 않은 것, 그 문자만 쓴 것, 이전 부분수열 뒤에 붙인 것 중 하나이다. 전이는 이 세 경우의 최대 길이를 정확히 계산하므로 각 상태는 정의한 최대 길이를 갖는다.

조건을 만족하는 수는 $6$ 또는 $7$로 나눈 나머지가 $0$이다. 따라서 $L$은 남길 수 있는 문자의 최대 개수이고, $N-L$은 삭제할 문자의 최소 개수이다. $L=0$이면 조건을 만족하는 비어 있지 않은 부분수열이 없다.

서브태스크 1은 모든 비어 있지 않은 부분수열을 조사하는 $O(N2^N)$ 풀이로 해결할 수 있다. 서브태스크 2는 마지막으로 고른 문자의 위치와 나머지를 상태로 두고, 앞선 모든 위치에서 전이하는 $O(N^2)$ 풀이로 해결할 수 있다. 전체 조건에서는 같은 나머지를 갖는 상태 중 최대 길이만 유지한다.

Solution written by GPT6