만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

곤란한 스트레이트 (Small)

면접 대비

시간 제한5초메모리 제한512 MB

요약
손에 든 카드를 연속된 숫자 묶음으로 나누어 가장 짧은 묶음을 최대한 길게 만듭니다.
난이도

보통10점 중 5점

유형
백트래킹, 정렬
정답자
아직 제출이 없습니다

문제

카드마다 정수 하나가 적혀 있는 카드 게임을 한다.

게임을 시작하면 카드 몇 장을 손에 받는다. 손에 든 카드는 한 장도 남기지 않고 여러 개의 스트레이트로 나눈다. 스트레이트는 값이 연속하는 카드의 집합이다. 예를 들어 카드 세 장으로 이루어진 {3, 4, 5}도 스트레이트고, 카드 한 장뿐인 {7}도 스트레이트다. 카드를 다 나누면 가장 짧은 스트레이트의 길이와 같은 금액을 달러로 받는다. 손에 카드가 없으면 스트레이트를 하나도 만들 수 없으므로 0달러를 받는다.

테스트 케이스마다 손에 든 카드가 주어진다. 각 테스트 케이스에서 받을 수 있는 최대 금액을 구한다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 각 테스트 케이스는 한 줄로 이루어진다. 각 줄에는 손에 든 카드의 개수 NN과 그 카드에 적힌 정수 NN개가 공백으로 구분되어 주어진다.

제한

  • 1≤T≤1001 \le T \le 100
  • 카드에 적힌 수는 1 이상 10000 이하다.
  • 0≤N≤100 \le N \le 10

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 그 테스트 케이스에서 받을 수 있는 최대 금액이다.

힌트

예제 입력의 첫 번째 케이스에는 1부터 10까지 적힌 카드 열 장이 있다. 길이가 10인 스트레이트 하나를 만들어 10달러를 받는다.

두 번째 케이스를 {101, 102, 103, 104, 105, 106}과 {103, 104}로 나누면 2달러를 받는다. 하지만 {101, 102, 103, 104}와 {103, 104, 105, 106}으로 나누면 4달러를 받는다.

세 번째 케이스는 카드가 없으므로 0달러다.

네 번째 케이스에서 9가 적힌 카드는 자기 혼자 있는 스트레이트에 들어가야 한다. 그래서 1달러를 받는다.

예제1

  1. 예제 1

    입력
    4
    10 1 2 3 4 5 10 9 8 7 6
    8 101 102 103 104 105 106 103 104
    0
    5 1 2 3 4 9
    
    예상 출력
    Case #1: 10
    Case #2: 4
    Case #3: 0
    Case #4: 1