BOJ 26976 - Feeding the Cows
그리디하게 앞에서부터 본다.
라면 에 를 설치하면 까지 인 소들을 모두 처리해줄 수 있다.
그런데 가 범위를 넘어갈 수 있고 이 경우 뒤에서부터 아직 채워지지 않은곳에 바로 채워주는 것으로 해결 가능하다.
void solve() {
int n, k;
cin >> n >> k;
string p;
cin >> p;
int g_last = -1, h_last = -1;
string ans = string(n, '.');
for (int i = 0; i < n; i++) {
if (p[i] == 'G') {
if (i <= g_last) continue;
int nxt = min(i + k, n - 1);
while (ans[nxt] != '.') nxt--;
ans[nxt] = 'G';
g_last = i + k * 2;
} else {
if (i <= h_last) continue;
int nxt = min(i + k, n - 1);
while (ans[nxt] != '.') nxt--;
ans[nxt] = 'H';
h_last = i + k * 2;
}
}
cout << n - cntt(ans, '.') << endl;
cout << ans << endl;
}
Comments