문제 8
1차원 사과게임
$1$차원 사과게임은 다음과 같이 진행된다.
게임보드의 초기 상태에는 $1$ 이상 $9$ 이하의 양의 정수 $n$개가 일렬로 나열되어 있다.
게임보드에 다음과 같은 작업을 $0$번 이상 수행할 수 있다.
- 합이 $10$인 연속된 $1$개 이상의 양의 정수를 모두 지운다.
게임보드에 남아 있을 수 있는 양의 정수의 개수의 최솟값을 구하라.
입력
첫 번째 줄에 정수 $n$이 주어진다. $(1 \le n \le 10)$
두 번째 줄에 게임보드의 초기 상태를 나타내는 정수 $A_1, A_2, \cdots, A_n$이 순서대로 공백으로 구분되어 주어진다. $(1 \le A_i \le 9)$
출력
게임보드에 남아 있을 수 있는 양의 정수의 개수의 최솟값을 출력한다.
예제 입력 1
5 6 3 1 9 7
예제 출력 1
1
예제 입력 2
6 1 2 3 4 5 6
예제 출력 2
2
공식 해설
$n\le10$이므로 남은 위치의 부분집합은 최대 $2^{10}$개이다. 삭제 순서 전체를 따로 기억하기보다 같은 게임보드에 도달한 경우들을 하나로 묶자.
남아 있는 원소만 상태로 두기
원소를 지워도 남은 원소들의 상대적인 순서는 바뀌지 않는다. 따라서 원래의 $n$개 위치 중 어떤 위치가 남았는지만 알면 현재 게임보드가 정해진다.
이를 $n$비트 정수로 나타내자. $i$번째 비트가 $1$이면 원래 $i$번째 원소가 남아 있다는 뜻이다. 처음에는 모든 비트가 $1$이다.
가능한 삭제를 모두 시도하기
한 상태에서는 남은 위치들을 원래 순서대로 나열한다. 이 나열에서 시작점을 하나씩 고르고, 오른쪽으로 원소를 더하며 합이 $10$인 구간을 찾는다. 값이 모두 양수이므로 합이 $10$을 넘으면 그 시작점에서는 더 볼 필요가 없다.
합이 $10$인 구간을 찾으면 그 원소들의 비트를 모두 끈 다음 상태로 이동한다. 삭제 후에는 원래 떨어져 있던 위치도 서로 이웃할 수 있으므로, 연속 구간은 원래 배열이 아니라 현재 남은 원소들의 순서에서 찾아야 한다.
이 과정을 DFS나 BFS로 탐색하되 같은 비트마스크는 한 번만 처리한다. 모든 합법적인 삭제를 빠짐없이 시도하므로 도달한 상태들은 만들 수 있는 게임보드와 정확히 같다. 처음 상태도 포함하여 켜진 비트 수의 최솟값을 구하면 된다.
상태가 최대 $2^n$개이고 상태마다 $O(n^2)$개의 구간을 확인하므로 시간복잡도는 $O(n^2 2^n)$이다. 방문 여부와 탐색 상태를 저장하는 공간복잡도는 $O(2^n+n)$이며, $n\le10$에서 충분하다.
구현 · 언어별 풀이
C++ 구현
남은 위치는 int 비트마스크, 방문 여부는 길이 1 << n인 배열로 저장한다. 초기 상태는 (1 << n) - 1이다.
C 구현
남은 위치를 int 비트마스크로 나타내고 visited[1 << n]에 방문을 기록한다. 상태 수가 최대 $1\,024$개이므로 배열 큐를 사용할 수 있다.
Python 구현
int 비트마스크와 길이 1 << n의 방문 배열을 사용한다.
Java 구현
마스크는 int, 방문 여부는 boolean[]로 둔다. ArrayDeque<Integer>로 상태를 탐색하면서 남은 숫자의 현재 순서를 복원한다. Integer.bitCount(mask)로 남은 개수를 구할 수 있다.
Rust 구현
마스크와 인덱스에는 usize, 방문에는 Vec<bool>을 쓴다. 남은 위치를 원래 순서대로 모아 구간 합을 검사하고, 삭제할 비트를 지운 새 마스크를 탐색한다. count_ones()로 개수를 센다.
JavaScript 구현
$n\le10$이므로 1 << n, mask & (1 << i) 같은 32비트 비트 연산으로 마스크를 다룰 수 있다. 방문 표시는 Uint8Array(1 << n)에 두고, DFS 스택에는 남은 위치의 마스크를 저장한다.