[BaekJoon] 1947 선물 전달 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int MAX = 1_000_000;
    static final int DIVISOR = 1_000_000_000;
    static int N;

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

        N = scanner.nextInt();
    }

    static void solution() {
        if(N == 1) System.out.println(0);
        else if(N == 2) System.out.println(1);
        else {
            int[] dp = new int[MAX + 1];
            dp[1] = 0;
            dp[2] = 1;

            for(int idx = 3; idx <= N; idx++) {
                long caseNum = ((long)(idx - 1) * (dp[idx - 1] + dp[idx - 2])) % DIVISOR;
                dp[idx] = (int) caseNum;
            }

            System.out.println(dp[N]);
        }
    }

    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.  접근

• 사람의 수에 따라 선물을 나누는 경우의 수를 나타내는 배열 dp를 생성합니다.
  • dp[n] = n명이서 선물을 나누는 경우의 수
• 1명일 때는 나눌 사람이 없기 때문에 0가지이고, 2명일 때는 서로 나눠야하기 때문에 1가지가 됩니다. 그러므로 dp[1], dp[2]는 각각 0과 1이 됩니다.
• 이후부터는 아래와 같은 규칙으로 찾아갑니다.
  • 현재 n명의 사람이 있다고 한다면, 1번 사람이 n번째 사람에게 선물을 준다고 가정합니다.
    • 만약 n번째 사람이 1번 사람에게 선물을 준다면, 1번과 n번 사람이 서로 교환한 상태이기 때문에 n - 2명의 사람이 서로 선물을 교환하는 경우의 수와 같습니다. 그러므로 dp[n - 2]가지 경우의 수를 가집니다.
    • 만약 n번째 사람이 1번 사람에게 선물을 주지 않는다면 1번이 n번에게만 선물을 준 상태이므로 n - 1명의 사람이 서로 선물을 교환하는 경우의 수와 같습니다. 그러므로 dp[n - 1]가지 경우의 수를 가집니다.
  • 위의 경우는 1번과 n번을 기준으로 봤었는데, 1번은 n번이 아닌 총 n - 1명에게 선물을 줄 수 있습니다.
  • 그러므로 위 두 가지 경우의 수의 합에 n - 1만큼 곱해주면 총 경우의 수가 되게 됩니다.
    • dp[n] = (n - 1)(dp[n - 2] + dp[n - 1])