BOJ 4576 Shut the Box

문제 링크:

문제 내용

당신은 다음과 같은 게임을 하려고 합니다.

• 양의 정수 $n$에 대해, 1부터 $n$까지 적힌 $n$장의 카드를 하나씩 앞면이 보이게 둡니다.
• $t$턴에 걸쳐서, $i$번째 턴에는 목표 수 $a_i$가 주어집니다. 이 턴에 당신은 앞면이 보이는 카드들 중에서 합이 $a_i$인 카드들을 골라서 뒤집어야 합니다. 이것이 불가능하면 이후의 모든 턴을 잃게 됩니다.

$n$, $t$, 그리고 $a_1, a_2, \cdots, a_t$가 주어질 때, 당신이 최종적으로 뒤집을 수 있는 카드의 최대 개수를 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 0 0으로 종료됩니다.

각 테스트 케이스에 대해, 첫 번째 줄에 $n$과 $t$가 주어집니다. ($1 \le n \le 22$, $1 \le t \le n$)

두 번째 줄에는 $a_1, a_2, \cdots, a_t$가 주어집니다. ($1 \le a_i \le 22$)

출력

각 테스트 케이스에 대해, Game {게임 번호}: {정답}의 형식으로 출력합니다.

문제 풀이