https://codeforces.com/contest/1506/problem/B
시간 2초, 메모리 256MB
input :
- t (1 ≤ t ≤ 500)
- n k(1 ≤ k ≤ n ≤ 50)
- string s of length n
output :
- For each test case output the minimum number of '*' characters that must be replaced with 'x' characters in order to satisfy the conditions above.
각 테스트 케이스에서 필요한 최소한의 '*'의 개수를 출력하시오.
조건 :
- You are given a number k and a string s of length n, consisting of the characters '.' and '*'. You want to replace some of the '*' characters with 'x' characters so that the following conditions are met:
The first character '*' in the original string should be replaced with 'x';
The last character '*' in the original string should be replaced with 'x';
The distance between two neighboring replaced characters 'x' must not exceed k (more formally, if you replaced characters at positions i and j (i<j) and at positions [i+1,j−1] there is no "x" symbol, then j−i must be no more than k).
k와 n길이의 문자열 s가 입력 됩니다. 이 문장은 '.'과 '*'로 이루어져 있습니다. 몇 개의 '*'를 'x'로 바꾸려고 합니다. 첫 번째 '*'은 'x'로 바뀌어야 합니다. 마지막 '*'은 'x'로 바뀌어야 합니다. 이웃하는 'x' 사이의 거리는 k를 넘어서는 안됩니다.(k까지는 okay)
조건이 좀 많은데 가장 중요한 것은 양 끝을 포함한다는 것이다.
이 부분에서 예외가 발생할 수 있다.
기본적으로 생각한 것은 이것이다.
'*'의 위치를 다 모은 다음에 k를 초과하는 별에서 그 이전 별을 추가한다. 이를 끝까지 반복하고 마지막에 위치하는 별이 마지막 별이 아닌 경우에는 마지막 별도 x로 바꾸도록 한다.
이 것을 리스트에 모두 저장을 한 다음에(인덱스를) 현재 가장 마지막에 추가한 x의 거리 차이를 계산하면서 반복을 하는 것이다.
import sys
for _ in range(int(sys.stdin.readline())):
n, k = map(int, sys.stdin.readline().split())
data = list(sys.stdin.readline().rstrip())
stars = []
for idx, item in enumerate(data):
if item == '*':
stars.append(idx)
if len(stars) == 1:
print(1)
continue
ans, now = 1, stars[0]
for i in range(1, len(stars)):
if now + k < stars[i]:
ans += 1
now = stars[i - 1]
print(ans if now == stars[-1] else ans + 1)
