[백준] 1767 N-Rook II

문제보기

import java.util.*;
import java.io.*;

public class Main{
  // 차례대로 n, m, k 일 때 가능한 경우의 수를 담는 변수
  static long[][][] d;
  static final int mod = 1000001;

  static long go(int n, int m, int k){
		// 만일 이 중 하나라도 음수라면 애초에 불가능한 짓을 한거니까 0 반환
    if( n < 0 || m < 0 || k < 0 ){
      return 0;
    }
    // 위에 안걸리면서 룩을 모두 소진한거라면 성공!
    if( k == 0 ){
      return 1;
    }
		
    // 메모된 값이 있다면 그걸 쓰자
    if(d[n][m][k] != -1){
      return d[n][m][k];
    }
		
    // 모든 경우의 수를 담을 변수
    long ans = 0;
		
    // 1. n번째 행에 룩을 놓지 않는 경우
    // n-1까지 진행된 경우의 수를 그대로 계승한다
    ans += go(n-1, m, k);
    
    // 2. n번째 행에 룩을 하나 놓는데, 아무에게도 공격받지 않는 경우
    // n-1까지 진행된 경우 중에서 m-1열까지만 있는 경우를 가져온다 
    // 왜냐하면 적어도 한 열은 비어있어야 아무에게도 공격받지 않기 때문
    // m개의 열 중 하나를 고르는것과 같으므로 mC1을 곱해준다
    ans += go(n-1, m-1, k-1)*m;
    
    // 3. n번째 행에 룩을 두개 놓는 경우
    // 이미 서로가 공격하고 있는 상황이므로 
    // 놓인 열에서는 아무에게도 공격받으면 안된다.
    // 즉 n-1까지 진행된 경우중에서 m-2열까지만 있는 경우르 가져온다
    // 그래야 적어도 2열은 깨끗 하자너...
    // 대신 mC2를 곱해야 한다
    ans += go(n-1, m-2, k-2)*m*(m-1)/2;
    
    // 4. n번째 행에 룩을 하나 놓는데, 
    // 이미 기존에 놓여진 룩에 의해 세로로 공격 받는 경우
    // 이건 사실 달리 말하면 행을 두개 잡아서 같은 열에 두개를 놓는거랑 같음
    // 따라서 n-2까지 진행된걸 가져오되 n-1C1 을 곱해줘야함
    // 마찬가지로 열 중에서 하나를 골라서 놓을거니까 mC1도 곱해줘야함
    ans += go(n-2, m-1, k-2)*m*(n-1);

    // 결과를 mod로 나누고 메모이제이션 해준다
    ans %= mod;
    d[n][m][k] = ans;
    return ans;

  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int m = Integer.parseInt(br.readLine());
    int k = Integer.parseInt(br.readLine());
    d = new long[n+1][m+1][k+1];

    for(int i = 0 ; i <= n ; i++){
      for(int j = 0 ; j <= m ; j++ ){
        Arrays.fill(d[i][j], -1);
      }
    }

    System.out.println(go(n, m, k));

  }
}

다이나믹적인 사고가 꽉 막힌 느낌이다 ㅠ

고딩때했던 귀납법이었나 그건 그냥 n = 1 일때 증명하고, n = k 일때 n = k+1 을 만족한다면 모든 n에 대해 해당 식이 성립한다.. 뭐 그런거 였는데(bottom up) top down은 반대 방식이라 익숙하지고 않고, 사고하기가 힘들다 .