[백준/1767] N-Rook II

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

1767번: N-Rook II

Difficulty : Platinum 3

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

체스 세계랭킹 1위의 숌은 더 이상 체스를 대결할 상대가 없자, 새로운 체스방법을 생각했다.

일단 Rook은 체스판의 같은 열, 혹은 같은 행에 다른 말이 있을 경우, 그 말을 공격할 수 있는 말이다.

숌은 N * M 크기의 체스판에 K개의 룩을 놓는데, 서로 공격받지 않는 경우의 수를 구하는 문제를 생각했다. 이 문제는 너무 쉽게 풀려서 숌은 좀 더 어려운 문제를 찾다가 각 룩이 최대 1개의 룩에만 공격받는 경우의 수가 궁금해졌다. 어떤 룩은 공격받지 않을 수도 있다.

N*M크기의 체스판이 주어졌을 때, K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 체스판의 세로 크기 N, 둘째 줄에 가로 크기 M, 셋째 줄에 놓으려고 하는 룩의 수 K가 주어진다.

 

출력

 

N * M 크기의 체스판에 K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 1,000,001로 나눈 나머지를 출력한다.

 

입력 예시

 

2
3
3

 

출력 예시

 

6

 

 

---

 

풀이

 

DP로 접근해 보자.

 

DP[i][j][k]를, i개 행과 j개 열을 가지고 있으며 룩이 조건에 맞게 K개 배치되어있는 경우의 수라고 가정하자. 우리는 DP[i][j][k]를 구하기 위해, i번째 열에 룩을 넣는 경우의 수를 모두 고려해 볼 수 있다.

 

• i번째 행에 룩을 1개도 넣지 않는 경우 : DP[i-1][j][k]
• i번째 행에 룩을 1개 넣는 경우 : 이 경우는 (i-1, j-1) 체스판을 먼저 고려해야 한다. 여기에 기존에 배치된 룩과 만나지 않도록 j개의 틈새 중 하나에 새로운 열을 추가하는 행위로도 볼 수 있다. 즉 값은 comb(j, 1) * DP[i-1][j-1][k-1]
• i번째 행에 룩을 2개 넣는 경우 : 이 경우는 (i-1, j-2) 체스판의 j개의 틈새 중 둘에 순서와 상관 없이 새로운 열을 중복하여 둘 추가하는 행위와 동일하다. 즉 값은 H(j-1, 2) * DP[i-1][j-2][k-2] = comb(j, 2) * DP[i-1][j-2][k-2]
• i번째 행과, 그 이전 행에 룩을 총 2개 넣는 경우 : 이 경우는 (i-2, j-1) 체스판을 고려하자. 열을 추가하는 행위는 comb(j,1)과 동일하다. 또한, 그 이전 행의 i-1개의 틈새 중 하나의 새로운 행을 추가로 삽입한다고 볼 수 있다. 즉 값은 comb(j, 1) * comb(i-1, 1) * DP[i-2][j-1][k-2]

총 O(NMK)의 시간복잡도로 풀 수 있다.

 

 

풀이 코드

MOD = 10**6 + 1
N = int(input())
M = int(input())
K = int(input())

dp = [[[0] * (K + 1) for _ in range(M + 1)] for _ in range(N + 1)]

for i in range(N+1) :
  for j in range(M+1) :
    dp[i][j][0] = 1

for k in range(1, K+1) :
  for i in range(1, N+1) :
    for j in range(1, M+1) :
      dp[i][j][k] = dp[i-1][j][k]
      dp[i][j][k] = (dp[i][j][k] + j * dp[i-1][j-1][k-1]) % MOD
      if k > 1 and j > 1 :
        dp[i][j][k] = (dp[i][j][k] + j * (j-1) * dp[i-1][j-2][k-2] // 2) % MOD
      if k > 1 and i > 1 :
        dp[i][j][k] = (dp[i][j][k] + j * (i-1) * dp[i-2][j-1][k-2]) % MOD

print(dp[-1][-1][-1])

풀이 완료!