[백준] 14578번 영훈이의 색칠공부

문제 설명

• https://www.acmicpc.net/problem/14578
• Gold 1

문제 풀이

• DP를 이용하여 풀이하였다.
• 1번 행부터 N번 행까지 파란 색을 선택하는 경우의 수 : N!
• 파란색을 정해놓고 각 행이 파란색 제외 서로 다른 열의 빨간색을 선택 하는 경우의 수 -> 교란 순열

  • DP(N) : N개 중에 서로 교차하지 않게 선택하는 경우의수 (교란 순열)
  • DP(N) = (N-1) * (DP(N-1) + DP(N-2))
    - 첫번째 선택하는 경우의 수 : N-1
    - 두번째 선택하되 첫번째 선택과 서로 교차해서 선택하고 이후 선택: DP(N-2)
    - 두번째 선택하되 첫번째 선택과 서로 교차하지 않게 선택하고 이후 선택 : DP(N-1)

• 문제의 답은 N! * DP(N)을 출력하면 된다.

소스 코드 (JAVA)

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

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static int N, MOD = 1000000007;

    static void solve() throws IOException {
        if ( N > 2 ) {
            long[] dp = new long[N + 1];
            long fact = 2;
            dp[1] = 0;
            dp[2] = 1;
            for (int i = 3; i <= N; i++) {
                dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD;
                fact = fact * i % MOD;
            }
            bw.write(fact * dp[N] % MOD+ "\n");
        } else {
            if (N == 1) bw.write("0\n");
            else bw.write("2\n");
        }
        bw.flush();
    }


    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * - N * N
 * - 파랑을 선택 하는 경우의 수 : N!
 * - 파랑이 선택 되고 빨강을 선택하는 경우의 수 : D(N)
 * - D(N) = (N-1) * (D(N-1) + D(N-2))
 */