BOJ 8415

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

 

 

코드

http://boj.kr/a2cc1f96953c4eb1accf307a94c67719

 

 Algorithmic Engagements PA 2006 7-5

 

난이도 : P1

 

Elapse Time : 실패

 

문제를 보고 이분 매칭의 개수가 $N$개가 될 수 있으면 룩을 놓을 방법이 존재한다는 것이므로 이분 매칭을 하는 것으로 문제를 풀기 시작했다. 매칭을 해놓고 변경할 수 있는 경우의 수를 dp등의 방법을 활용해 세어보는 풀이를 생각해 보았는데 풀이가 생각나지 않았고 다른 풀이를 찾지 못했다.

 

시간을 두고 생각하다가 정사각 행렬의 determinant를 생각해보게 되었는데 홀짝성만 판단하면 되는 이 문제와 큰 관련이 있을 것 같다는 생각이 들었다. determinant의 식 특성상 모든 permutation을 다 살펴보게 되고 determinant의 홀짝성과 룩을 놓는 경우의 수의 홀짝성이 동일하다는 것을 알게 되었다. 하지만 determinant의 값을 구하는 것이 문제였다. 처음에는 determinant가 0 또는 1이라고 착각하여 쉽게 구할 수 있다고 생각했지만 가우스 소거법을 쓰다 보면 1과 0이 아닌 다른 숫자가 나오기 시작하면서 determinant를 구하기 힘들게 만들었다. 우선 int 자료형으로 계산을 먼저 했는데 오버플로우가 나는 test case가 없었는지 AC를 받았다. 그러나 이게 정풀이 아닐 것 같다는 생각이 들어 jhwest2님의 코드를 참고했고 determinant의 홀짝성만이 중요한 요소이기 때문에 값을 계산하는 것이 아니라 bitset을 활용하여 홀짝성만 판단할 수 있다는 것을 알게 되었다.