시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 38 | 2 | 2 | 5.263% |
A, C, G, U로 이루어진 문자열 S가 주어졌을 때, 만들 수 있는 짝의 개수 중에서 최댓값을 구하는 프로그램을 작성하시오.
짝은 다음과 같은 조건을 지켜야 한다.
문자열 S가 RLE 인코딩한 형태로 주어졌을 때, 만들 수 있는 짝의 최대 개수를 구하는 프로그램을 작성하시오.
RLE 인코딩이란, 연속된 같은 문자가 몇 번 등장하는지 정수로 나타낸 인코딩을 의미한다. 예를 들어, "AAAACCGAAUUG"는 "A4C2G1A2U2G1"로 인코딩할 수 있다. 즉, <c1f1c2f2c3f3...cnfn>의 형태로 입력이 주어지며, ci는 A, C, G, U중 하나, fi는 양의 정수이다.
입력으로 주어지는 문자열은 다음과 같은 4가지 조건을 만족한다.
첫째 줄에 테스트 케이스의 개수 T (T ≤ 200)가 주어진다. 첫째 줄에는 문자열 S가 RLE 인코딩한 형태로 주어지며, 둘째 줄에는 K (0 ≤ K ≤ 20)가 주어진다.
각각의 테스트 케이스에 대해서, 만들 수 있는 짝의 최대 개수를 출력한다.
3 A3C1G1C1U4A2U1 1 A3C1G1C1U4A2U1 0 A100U200 2
Case 1: 6 Case 2: 5 Case 3: 100
첫 번째 예제의 경우에 아래와 같이 6개의 짝을 만들 수 있다.
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2012 D번