시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 58 | 12 | 5 | 17.241% |
선영이는 테트리스 같은 게임을 하고 있다.
게임은 비어있는 세 열에서 시작한다. 게임이 진행되는 동안 글자가 하나씩 화면의 가장 위에 보여진다. 글자가 보여지면, 선영이는 세 열중 하나를 선택한다. 선택한 열이 비어있다면, 그 열의 가장 아래에 글자를 놓고, 비어있지 않다면, 그 열의 가장 위에 있는 단어의 위에 글자를 놓는다.
게임이 끝난 후에 선영이가 얻은 점수는 각 열의 점수의 합이다. 각 열의 점수는 다음과 같이 계산할 수 있다.
먼저, 동일한 단어로 이루어진 그룹을 모두 찾는다.
예를 들어, 어떤 열의 글자가 아래 그림과 같다고 하자.
A A A B C C C A A
위의 그림에는 총 4개의 그룹이 있다. 그 다음, 각 그룹의 크기(포함되어 있는 글자의 개수)에 따라서 점수를 계산하면 된다.
예를 들어, 크기가 1인 그룹은 3점, 2인 그룹은 7점, 3인 그룹은 5점이라고 한다면, 위의 그림은 5+3+5+7=20점이 된다.
각 그룹의 점수와 화면의 가장 위에 보여지는 글자가 순서대로 주어진다. 이때, 선영이가 테트리스 같은 게임에서 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오.
첫째 줄에 다섯 개의 자연수 B1, B2, B3, B4, B5가 주어진다. i=1, 2, 3, 4인 경우에 Bi는 글자 i개로 이루어진 그룹의 점수이고, B5는 글자 5개 또는 그 이상으로 이루어진 그룹의 점수이다. 이 다섯 자연수는 100보다 작거나 같다.
둘째 줄에는 화면에 보여지는 글자의 개수 N이 주어진다. (1 ≤ N ≤ 1000)
셋째 줄에는 화면에 보여지는 글자 N개가 순서대로 주어진다. 글자는 알파벳 대문자이다.
첫째 줄에 선영이가 얻을 수 있는 가장 높은 점수를 출력한다.
5 5 5 5 5 9 ABCABCABC
45
| | |CAB| |BCA| |ABC| +---+
1 5 1 1 1 9 ABCABCABC
18
| | |BCA| |ABC| |ABC| +---+
3 3 10 3 3 17 AAABBCCCAAACBAAAB
56
| | |A | |A | |A | |B | |A | |A | |A | |C | |ABC| |ABC| |ABC| +---+