[BaekJoon] 14578 영훈이의 색칠공부 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int DIVISOR = 1_000_000_007;

    static int size;

    static void input() {
        Reader scanner = new Reader();

        size = scanner.nextInt();
    }

    // 교란 순열 문제
    //  - 빨간색 혹은 파란색 두 가지 색으로 칠해야 하니, 두 색 중 하나의 색을 먼저 놓는 경우를 생각해보자
    //  - 예를 들어, 빨간색을 먼저 놓는다고 생각한다면,
    //      - 예시에서 주어진 3 x 3 격자가 있을 때, (1, 1), (2, 2), (3, 3)에 빨간색을 칠한다고 가정하자
    //      - 그럼 파란색은 (1, x), (2, y), (3, z)에 있어야 하는데, x는 2, 3, y는 1, 3, z는 1, 2가 가능하다
    //          -> 이 때, x가 2가 되면, z는 1만 가능하고, y는 3만 가능하다
    //          -> x가 3이 되면, y는 1만 가능하고, z는 2만 가능하다
    //      - x ~ z가 모두 중복되지 않은 특정한 값을 제외하고 모두 허용된다!
    //          -> 교란 순열 문제!

    // 그림의 크기가 1이면 두 색을 사용할 수 없으므로 경우의 수가 0
    // 그림의 크기가 2이면 빨간색과 파란색을 번갈아가며 사용하면 경우의 수가 2
    // 교란 순열 점화식
    //      - dp[length] = (length - 1) * (dp[length - 1] + dp[length - 2])
    //      - 이 점화식을 이용해 구한다!
    static void solution() {
        if(size == 1) {
            System.out.println(0);
        } else if(size == 2) {
            System.out.println(2);
        } else {
            long[] dp = new long[size + 1];
            long caseNum = 2;

            dp[0] = dp[1] = 0L;
            dp[2] = 1L;

            for(int length = 3; length <= size; length++) {
                dp[length] = (length - 1) * (dp[length - 1] + dp[length - 2]);
                dp[length] %= DIVISOR;

                caseNum *= length;
                caseNum %= DIVISOR;
            }

            System.out.println((caseNum * dp[size]) % DIVISOR);
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

교란 순열(완전 순열)

모든 원소의 위치를 바꾸는 순열

다음 문제를 생각해보자

n명의 사람이 각각 자신의 모자를 벗었다가 아무 모자나 다시 쓰는데, 모든 사람이 자기 것이 아닌 모자를 쓰는 경우의 수는?

• 이 문제와 같이 고정점을 갖지 않는 순열의 개수를 묻는 문제를 교란 순열이라고 한다.

점화식

$D_n = \begin{cases} 0 &\text{if n = 1} \\ 1 &\text{if n = 2} \\ (n - 1)(D_{n - 1} + D_{n - 2}) &\text{otherwise} \end{cases}$