BOJ 11928 공기놀이

문제 링크 : https://www.acmicpc.net/problem/11928

(1) n이 홀수인 경우의 답은 이 되고, (2) n이 짝수인 경우의 답은 가 된다.

먼저 (1)의 풀이를 살펴보자. 편의를 위해 R을 빨간 돌, B를 파란 돌이라 하자.

R이 B의 왼쪽에 있는 게 홀수 개인 가짓수를 세아리자. R을 n개와 B를 n개 늘어놓은 것 중 하나를 a라 하고, 그걸 거꾸로 나열한 걸 b라 하자. 그러면 a에서 (R,B)의 개수는 b에서 (B,R)의 개수와 같고, 즉 a,b에서의 (R,B)의 개수의 합은 a에서의 (R,B)와 (B,R)의 개수를 세는 것이 된다. 이는 R 중 하나, B 중 하나를 택하기만 하면 되므로 총 개로 홀수이다. 따라서 a에서 (R,B)의 개수가 홀수였다면 b는 짝수이고, a가 짝수였다면 b는 홀수이다. 따라서 이것은 짝수인 것과 홀수인 것의 일대일 대응이 되고 그 개수는 같아야 한다. 따라서 답은 전체 개의 절반인 이다. 이 풀이는 (2)에선 적용되지 않는다. 왜냐하면 이 짝수이기 때문에, 짝수인 것과 홀수인 것의 일대일 대응인 것을 보일 수가 없기 때문이다.

다음은 (1)과 (2) 모두에 사용 가능한 해법이다. 먼저 (2)부터 고려하자. (R,B)의 개수가 홀수인 것의 집합을 A라 하고, 짝수인 것의 집합을 B라 하자. 이 때 다음과 같은 대응 을 생각하자. 먼저, A의 임의의 원소 a를 두 자리씩 나눈다. 예를 들면, RR/BB/BB/RB/RR/BR 이런 식으로 두 자리씩 나눈다. 그러면 만약 RB나 BR가 나오지 않으면 로 정의하고, RB나 BR가 하나 이상 나오면 최초로 나오는 RB나 BR를 각각 BR와 RB로 바꾼 것을 로 정의한다. 그러면 이 경우는 (R,B)의 쌍의 개수가 정확히 하나 바뀌기 때문에는 B에 속한다. 마찬가지로 B의 원소에 대해서도 똑같이 정의한다. 그러면 A와 B의 원소들 중에서 RB나 BR가 나오지 않는 것들을 제외하곤 A와 B가 일대일 대응이 된다. 그런데 RB와 BR가 없다는 것은 곧 두 자리로 나눈 결과가 RR과 BB만 나오는 것인데, 이 때 (R,B)의 개수는 반드시 짝수다. 즉, 그런 것들은 모두 B의 원소이다. 개수는 RR n/2개와 BB n/2개를 배열하는 가지수이므로 이다. 즉, A의 원소와 B의 원소 중 개를 제외한 것들이 일대일 대응이 되므로 A의 원소의 개수(구하려는 값)를 라 하면 이다. 이므로, 답은 이다. 마찬가지 풀이를 n이 홀수일 때에도 적용할 수 있다. 이 경우 RB와 BR가 없는 경우가 없다. 즉 R이 홀수, B가 짝수개 있으므로 반드시 두 개씩 나눌 때 RB나 BR가 등장한다. 따라서 A와 B가 일대일 대응이 되고, 가짓수는 전체의 반이 되어 같은 답이 나온다.