BOJ 26976 - Feeding the Cows

BOJ 26976 - Feeding the Cows

그리디하게 앞에서부터 본다.

$s_i=G$ 라면 $s_i+k$에 $G$를 설치하면 $[s_i, s_i+2k]$ 까지 $s_i=G$ 인 소들을 모두 처리해줄 수 있다.

그런데 $s_i+k$ 가 범위를 넘어갈 수 있고 이 경우 뒤에서부터 아직 채워지지 않은곳에 바로 채워주는 것으로 해결 가능하다.

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;
}