📙[Algo] BOJ10978. 기숙사 재배정

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

문제 요약

• N명의 학생이 있고 N개의 기숙사가 있다
• 모든 학생들은 본인이 살았던 봄학기 기숙사에서 가을 학기에 다른 기숙사로 배정되면 이사를 해야하므로 기숙사 재배정을 신청하였다
• 이렇게 모든 학생들은 기숙사 재배정을 신청했지만, 학생복지팀에서는 어떤 학생에게도 기숙사 재배정을 해주지 않으려고 한다.
• 봄학기때 기숙사를 이미 배정받은 상태에서, 가을학기 기숙사에 아무도 재배정이 되지 않는 경우의 수를 구해보자

시간 제한

• 1초

입력

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 각 케이스의 첫 번째 줄에 학생 명수(기숙사의 개수) N (1 ≤ N ≤ 20) 이 주어진다.

출력

• 각 테스트 케이스 별로 아무도 재배정이 되지 않는 경우의 수를 출력한다.

접근법

• 문제를 잘 이해해보면, 학생들이 첫날 배정받은 기숙사가 아닌 다른 기숙사를 재배정 받을 경우 가능한 경우의 수를 구하는 문제이다. (문제에서 재배정을 하지 않은 모든 경우의 수를 구하라 했으므로)
• 따라서, 만약 학생들 번호가 0 ~ N-1이고, 처음 배정받은 기숙사번호도 각각 0~N-1이라 가정했을 때,
  • 현재 번호랑 일치하지 않는 경우(cur != i)만 기숙사를 선택했다.
  • 이때, 중복해서 기숙사를 배정하면 안되므로 방문체크를 해야하는데, 나는 비트마스킹으로 처리했다. ⇒ 나중에 DP메모이제이션 할 때, 지금까지 선택한 값도 고려하기 위해서
• N이 20이기 때문에, 학생마다 최대 19개씩 선택할 수 있으므로 시간초과가 뜬다.(19^20) ⇒ 따라서 dp메모이제이션으로 중복 계산을 없앴다.

코드

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

public class Main {
    static int N;
    static long[][] dp = new long[21][1 << 20];

    static long recur(int cur, int state) {
        if (cur == N) return 1;

        if (dp[cur][state] != -1) return dp[cur][state];

        long ret = 0;
        for (int i = 0; i < N; i++) {
            if (cur == i || (state & (1 << i)) > 0) continue;
            ret += recur(cur + 1, state | (1 << i));
        }

        dp[cur][state] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        long ret;
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            for (long[] d1 : dp) {
                Arrays.fill(d1, -1);
            }

            ret = recur(0, 0);
            sb.append(ret).append("\\n");
        }
        System.out.println(sb);
    }
}