시간 제한: 1 초 / 메모리 제한: 128 MB
\(1\)차원 사과게임은 다음과 같이 진행된다.
게임보드의 초기상태에는 \(1\) 이상 \(9\) 이하의 자연수 \(n\)개가 일렬로 나열되어 있다.
게임보드에 다음과 같은 작업을 \(0\)번 이상 수행할 수 있다.
게임보드에 남아있을 수 있는 자연수의 개수의 최솟값을 구하시오.
첫 번째 줄에 초기상태의 자연수의 개수 \(n\) \((1\leq n\leq 10)\)이 주어진다.
두 번째 줄에 \(1\) 이상 \(9\) 이하의 자연수 \(n\)개가 순서대로 주어진다.
게임보드에 남아있을 수 있는 자연수의 개수의 최솟값을 출력한다.
5
6 3 1 9 7
1
\([6,3,1,9,7]\rightarrow [6,3,7]\rightarrow [6]\)으로 자연수가 \(1\)개 남았을 때가 최소임을 증명할 수 있다.
\([6,3,1,9,7]\rightarrow [9,7]\)도 가능하지만 남아있는 자연수의 개수가 최소가 아니다.
6
1 2 3 4 5 6
2