[JAVA] 백준 1767번 N-Rook II

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

1767번: N-Rook II

이 문제는 풀이를 보고 한참을 이해하지 못했는데,

내가 애초에 문제를 잘못 이해했기 때문이라는 것을 알았다.. 원래도 어려웠지만 그래서 더더욱 어려웠다....

[각 룩이 최대 1개의 룩에만 공격받는 경우의 수] 라는 것은 각 룩이 공격을 받지 않을 수도 있고, 받는다면 1개의 룩에게만 공격을 받는다. 이것은 모든 각각의 룩에게 적용이 되는 룰이다.

룩을 어느 자리에 하나 놓으면 그 룩이 속한 행이나 열에는 다른 하나의 룩만 놓거나 놓지 않을 수 있다.

그렇다면, 아래와 같이 네가지 경우의 수를 생각해보자.

 

1. 행에 룩을 놓지 않는 경우 (21번째 줄) → 공격받지 않음(공격받을 룩이 없음)

2. 행에 하나만 두는 경우 (22번째 줄) → 공격받지 않음

3. 행에 두개 두는 경우 (23번째 줄) → 행에서 공격받음

4. 열에 두개 두는 경우 (24번째 줄) → 열에서 공격받음

 

d[n][m][k] = d[행][열][룩의 수] 로 변수를 설정하고 경우의 수를 살펴보자.

 

1. 행에 룩을 놓지 않는 경우

→ 남은 룩의 수(k)는 그대로 인데, 한 행은 룩을 놓지 않는다 가정했으니 사용할 수 있는 행이 하나 줄어든다.

d[n][m][k] += d[n-1][m][k] 가 된다.

(나는 처음에 행과 열 모두에 룩이 속하지 않는다 생각하고 d[n-1][m-1][k] 라고 생각했으나, 그렇게 하면 첫번째 행 이외의 행에 룩을 두는 경우들도 제외되면서 행에 룩을 하나 두는 경우인 2번과 겹치므로, 한 행씩 설정한다.)

 

2. 행에 룩을 하나만 두는 경우

룩이 위치한 열은 다른 룩을 둘 수 없다.(회색칠한부분)

룩을 둘 수 있는 경우의 수는 열의 수 만큼 있다.(*m)

d[n][m][k] += d[n-1][m-1][k-1] * m

 

여기서 헷갈렸던 부분은 룩을 어느 열에 두느냐에 따라서 d[n-1][m-1][k-1]값이 달라지는 것이 아닌가? 하는 부분이었다.

하지만, 룩이 공격받는 경우는 같은 행, 같은 열에 속하는 경우이기 때문에 상관이 없었다..!!

아래 그림 두 경우를 다른 케이스로 보고 unique한 index 값을 줘서 구분해야 한다고 생각했으나 행, 열 개수에 따라서 놓는 경우의 수는 같았다. 같은 값인 d[n-1][m-1]를 가지고 있는 것이다. 룩의 위치에 따라서 최대 하나의 룩에게만 공격받는 경우는 같은 행, 열에 위치한 경우만 보는 것이기 때문에 회색 열이 중간에 있든, 앞에 있든 상관이 없었다.

 

3. 행에 룩을 두개 두는 경우

아래 그림에서 회색부분이 한 행에 룩을 두개 두었을때 차지하는 자리이고,

노란색 부분이 룩을 둘 수 있는 남은 경우의 수이다.

룩이 올 수 있는 경우의 수는 열의 개수에서 2개를 선택하는 경우의 수인 (m * (m-1)) / 2 이다.

d[n][m][k] += d[n-1][m-2][k-2] * m * (m-1) / 2

 

4. 열에 룩을 두개 두는 경우

아래 그림에서 회색부분이 열에 룩을 두개 두는 경우 차지하는 자리이다.

룩이 올 수 있는 경우의 수는 m * (n-1)  이다. (m이 열, 가로 칸 개수 * 남은 행, 남은 세로 개수)

d[n][m][k] += d[n-2][m-1][k-2] * m * (n-1)

여기서 행은 첫번째 행은 이미 선택된 것으로 가정하고, 나머지 행 중에 하나를 고르는 것이기 때문에 (n-1)값을 곱해주는 것이고

2번에서 설명한 것과 마찬가지로 어느 행을 선택하든 d[n-2][m-1][k-2]의 값은 동일하다.

 

위 원리를 이용해서 풀면 DP 방법으로 풀 수 있는데, 어려웠던 부분을 적어본다.

 

먼저, 문제를 잘못 이해했다. 각 룩이 최대 1개의 룩에게 공격을 받는다는건데 최대가 아니라 무조건 1개라고 문제를 잘못 봤다..

그래서 답 풀이를 봤을 때, 룩이 공격받는 경우의 수도 배열에 넣어주어야 하는게 아닌가..? 하고 생각하느라 시간을 보냈다.

 

그리고 각 룩이 공격받는지를 확인하는 것이기 때문에 처음 행, 열에서의 경우의 수를 계산하고 그 행, 열을 제외하면 그 다음 행, 열에서의 계산은 독립적으로 누적 합을 구할 수 있다.

 

마지막으로, 룩이 위치한 부분을 기록할 필요가 없다는 점을 생각하지 못했다. 위에서 2번 행에 룩을 하나만 두는 경우를 설명하면서 언급했던 부분인데, 룩을 어느 행이나 열에 두냐에 따라 unique한 값으로 메모리에 저장해줘야 한다고 생각했는데 그럴 필요가 없었다. 각 룩이 공격받는 경우는 같은 행, 같은 열이면 되기 때문에 위에 그림에서 노란 부분을 합치면 어차피 같기 때문이고 그 수에 경우의 수만큼 곱해주면 되는 것이었다!