BOJ 23085 - 판치기

BOJ 23085 - 판치기

$N$이 작으므로 BFS로 풀어줄 수 있다.

현재 상태를 $H$가 몇개가 있는지로 두자.

현재 개수에서 $H$를 $x$개 뒤집기로 했다면, $T$는 $k-x$ 개 뒤집는다.

그럼 결국 $T$가 $x$개 생기고 $H$가 $k-x$개 생기므로 $H$는 $k-2x$ 개 생긴다.

이렇게 BFS로 최단경로를 돌려주면 된다.

void solve() {  
   int n, k;  
   string s;  
   cin >> n >> k >> s;  
   int h = cntt(s, 'H');  
   vi vis(n + 1);  
   queue<int> q;  
   q.push(h);  
   vis[h] = 1;  
   int ans = 0;  
   while (sz(q)) {  
      int size = sz(q);  
      while (size--) {  
         int cur = q.front();  
         if (cur == 0) goto out;  
         q.pop();  
         for (int h = 0; h <= k; h++) {  
            int t = k - h;  
            int nxt = cur - h + t;  
            if (cur >= h && n - cur >= t && !vis[nxt]) {  
               vis[nxt] = 1;  
               q.push(nxt);  
            }  
         }  
      }  
      ans++;  
   }  
   out:;  
   cout << (!vis[0] ? -1 : ans);  
}