6233 - Face The Right Way

문제 링크

---

https://www.acmicpc.net/problem/6233

문제 요약

---

\(N\)마리의 소들이 일렬로 서 있다. 이 소들은 앞을 보고 있거나 뒤를 보고 있다. 이 때 이 소들에 대해서 다음과 같은 연산을 할 수 있다.

1. 특정 길이 \(L\)을 정한다. 이 값은 변하지 않는다.

2. 정확히 \(L\)마리의 연속된 소들의 상태를 반전시킬 수 있다.

3. 상태를 반전시킨다는 것은 앞을 보고 있는 소는 뒤를 보고, 뒤를 보고 있는 소들은 앞을 보는것이다.

2번 연산을 최소한으로 사용해 모든 소들을 앞을 보게 하는것이 문제다. 만약 최소한의 연산 횟수를 가지는 \(L\)이 여러가지면 그중에 작은것을 출력한다.

문제 풀이

---

우선 문제를 간단하게 만들기 위해 \(L\)이 정해져 있다고 생각을 해보자. 그렇다면 최선의 선택을 어떻게 할 수 있을까? 곰곰이 생각해 본다면 동일한 구간에 똑같은 연산은 두번 이상 한다는 것은 의미가 없다는 것을 알 수 있다. 즉 어떠한 구간 \([i,\ i+L)\)에 적용할 수 있는 연산의 횟수는 0번 또는 1번이라는 것이다. 이 생각을 토대로 \(greedy\)로 접근을 해볼 수 있다.

가장 왼쪽에 있는 소부터 봐 가면서 뒤를 보고있으면 그 소부터 연속된 \(L\)마리에 연산을 적용시킨다. 그렇다면 가장 왼쪽에 있는 소는 앞을 보게 될 것이다. 그 다음 소로 넘어가서 이와 같은 방법을 계속 반복한다. 그리고 가능한 모든 연산이 끝난 뒤 모든 소들이 앞을 보고 있는지 확인하다. 이렇게 길이 \(L\)에 대해 모든 소들을 앞을 볼 수 있게 하는 가능한 길이인지, 최소한의 연산횟수는 몇번인지 알 수 있다.

그렇다면 구현은 어떻게 해야할까? 가장 간단한 방법은 매번 연산이 있을때마다 직접 시뮬레이션을 해 주는 것이다. 그렇게 된다면 특정 길이 \(L\)에 대해서 \(O(N^2)\)에 풀 수 있다. 하지만 우리는 이 시간을 개선시킬 수 있다. 해당 위치에 연산이 몇번 누적되었는지만 유지를 해주면 되기 때문이다. 이는 \(partial\ sum\)을 구하는 과정과 비슷하게 계산을 할 수 있다. 그렇다면 우리는 \(O(N)\)에 확인을 할 수 있다.

자 이제 특정 \(L\)에 대해 확인을 하는 작업이 끝났다. 이제 가능한 모든 \(L\)에 대해 확인을 해주면 된다. 그렇다면 \(O(N^2)\)이 걸리겠지만 N이 \(5000\)밖에 안되기 때문에 충분기 가능한 시간복잡도다.

소스 코드

---

#include <stdio.h>
#include <string.h>

const int INF = 987654321;
int n, ans = INF, len = INF, A[5010], P[5010];
char ch;

int func(int L) {
  memset(P, 0, sizeof(P));
  int ret = 0, cnt = 0;
  for (int i = 0 ; i < n ; ++i) {
    cnt += P[i];
    if (A[i] ^ (cnt & 1)) {
      if (i + L > n) {
        return INF;
      }
      ++cnt;
      ++ret;
      P[i + L] += -1;
    }
  }
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 0 ; i < n ; ++i) {
    scanf("\n%c", &ch);
    A[i] = ch == 'B' ? 1 : 0;
  }
  for (int i = 1 ; i <= n ; ++i) {
    int ret = func(i);
    if (ret < ans) {
      ans = ret;
      len = i;
    }
  }
  printf("%d %d\n", len, ans);
}