시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 90 | 2 | 1 | 100.000% |
색(빨간색, 노란색, 초록색, 파란색) 이 있는 타일에 숫자가 적혀있다. 타일의 정보는 다음과 같이 주어진다. 1r은 빨간색 타일에 1이 적힌 것을 의미하고, 3y는 노란색 타일에 3이 적힌 것을 의미한다. 즉, 앞에 있는 숫자는 타일에 적힌 숫자를 의미하고, 뒤에 있는 알파벳 소문자는 색을 의미한다. (r : 빨간색, y : 노란색, g : 초록색, b : 파란색)
이러한 타일을 가지고 게임을 하려 한다. 같은 색의 타일이고 연속된 숫자의 타일을 3개 이상 제거 시키면 그 연속된 숫자의 합만큼 점수를 얻게 된다. 예를 들면 9r, 10r, 11r 을 제거시키면 30점을 얻게 되고, 60g, 61g, 62g, 63g, 64g, 65g를 선택하면 374점의 점수를 얻게 된다. 그리고 같은 숫자이고 다른 색의 타일을 3개 이상 제거 시키면, 역시 그 타일들의 숫자의 합만큼 점수를 얻게 된다. 예를 들어 1r, 1g, 1b 를 제거 시키면 3점을, 17r, 17g, 17b, 17y를 제거시키면 68점을 얻게 된다.
이러한 규칙으로 타일을 제거 시킬 때, 최대한 점수를 많이 얻으려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오. (타일을 선택하면 제거시켜야 하므로 같은 타일을 두 번 더할 수는 없다.)
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.
각 테스트 케이스마다 가능한 최대 점수를 한 줄에 하나씩 출력한다.
3 5 7g 7b 7r 8r 9r 7 23b 1y 24b 1r 93b 1b 100r 8 2y 2r 2g 2b 4g 5g 6g 7g
24 3 30