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가 짝..
2016. 2. 10.
