【백준】- 14515. Yin and Yang Stones

문제

본 문제는 외국어 문제이기에, 제가 문제 번역을 작성해 두었습니다. 아래의 링크를 참고해 주세요!

https://www.acmicpc.net/board/view/104727

글 읽기 - 【번역】14515. 음양

풀이

문자열 $S$ 의 길이가 최대 $100,000$ 이기에, 돌을 선택하는 모든 방법을 일일이 모두 따져보는 방법은 너무 시간이 오래 걸리게 됩니다. 돌을 하나만 선택할 수 있다고 가정해도 그 가짓수는 무려 $100,000 \times 99,999 \times ... \times 2 \times 1$ 가지나 됩니다. 그 대신, 우리가 할 수 있는 연산에서 규칙을 찾아 봅시다.

1. 검은색 돌을 흰색 돌보다 $1$ 개 더 많도록 연속하게 돌을 선택한 후, 검은 돌 $1$ 개로 합성한다.
2. 흰색 돌을 검은색 돌보다 $1$ 개 더 많도록 연속하게 돌을 선택한 후, 흰색 돌 $1$ 개로 합성한다.

위의 연산에서, 없어지는 돌의 개수만을 중점으로 생각해 본다면 어떻게 될까요?

 

1번 연산의 경우 검은색 돌을 $K + 1$ 개 선택하고, 흰색 돌을 $K$ 개 선택해 본다고 가정해 봅시다.

연산 후에는 검은색 돌 한 개만 남게 되므로 검은색 돌이 $K$ 개, 흰색 돌이 $K$ 개 없어지게 됨을 알 수 있습니다. 2번 연산도 마찬가지로 검은색 돌과 흰색 돌이 각각 $K$ 개 없어지게 됨을 알 수 있습니다.

그렇기에 우리가 사용할 수 있는 연산은 아래와 같이 바꿀 수 있습니다.

1. 어느 한쪽의 색의 돌이 $1$ 개 더 많도록 돌을 선택한 뒤, 각 색의 돌을 $K$ 개씩 없앤다.

같은 개수의 돌이 없어진다는 것이 연산의 핵심인 것 같으니, 이제 처음에 주어지는 검은색 돌과 흰색 돌의 개수가 같은지, 다른지에 따라 나누어서 생각해 볼까요?

1. 검은색 돌과 흰색 돌의 개수가 같은 경우

처음에 각 색깔의 돌이 각각 $K$ 개씩 있고, 위의 연산을 적절히 활용해 정확히 각 색깔의 돌을 $K - 1$ 개씩 지울 수 있다면, 각 색깔의 돌을 $1$ 개씩 남게 할 수 있게 되어 돌들을 균형잡히게 만들 수 있습니다. 그런 방법이 있을까요? 네!

검은색 돌을 제외한 모든 돌을 선택하면 검은색 돌 $K - 1$개, 흰색 돌 $K$ 개를 선택할 수 있습니다. 이 상태에서 2번 연산을 수행한다면 각 색깔의 돌을 정확히 $K - 1$ 개씩 없앨 수 있습니다. 돌들이 원형으로 나열되어 있기 때문에 제외하는 검은색 돌이 어디에 있든 항상 선택하는 것이 가능합니다.

이 방법은 검은색 돌과 흰색 돌의 개수가 같다면 항상 사용할 수 있는 방법이므로, 검은색 돌과 흰색 돌의 개수가 같다면 항상 돌들을 균형잡히게 만들 수 있습니다.

2. 검은색 돌과 흰색 돌의 개수가 다른 경우

위에서 제가 설명했듯이, 어떤 연산을 선택하든 같은 개수의 돌이 없어지게 됩니다. 그렇기 때문에, 처음에 주어진 검은색 돌과 흰색 돌의 개수가 다르다면 어떻게 연산을 해도 두 색깔의 돌에서 같은 개수의 돌만을 없앨 수 있기 때문에, 절대로 돌의 개수가 같도록 만들 수 없습니다.

검은색 돌과 흰색 돌의 개수가 다르다면 돌들을 균형잡히게 만드는 것이 항상 불가능합니다.

 

이제 우리가 해 줘야 하는 것은, 검은색 돌과 흰색 돌의 개수가 같은지만을 판별하는 것 뿐이네요! 문자열의 처음부터 끝까지 모든 돌의 개수를 세 주면 되므로, 시간복잡도는 $O(S$의 길이$)$ 가 됩니다. 제한 시간 내에 충분히 모든 연산을 진행할 수 있죠.

 

코드

• C++17

#include <iostream>
#include <string>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int white_count = 0;
    int black_count = 0;

    string S;
    cin >> S;

    for (size_t i = 0; i < S.size(); i++) {
        if (S[i] == 'W') {
            white_count += 1;
        } else {
            black_count += 1;
        }
    }

    if (white_count == black_count) {
        cout << 1;
    } else {
        cout << 0;
    }
}

• Python 3

stones = list(input())
print(1 if stones.count('B') == stones.count('W') else 0)

• Node.js

const stones = require('fs')
  .readFileSync(0, 'utf-8')
  .trim();

let whiteCount = 0;
let blackCount = 0;

for (let index = 0; index < stones.length; index++) {
  if (stones[index] === 'W') {
    whiteCount += 1;
  } else {
    blackCount += 1;
  }
}

console.log(whiteCount === blackCount ? 1 : 0);