[BaekJoon] 1176 섞기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int studentCount;
    static int minDiff;
    static int[] heights;
    static long[][] dp;

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

        studentCount = scanner.nextInt();
        minDiff = scanner.nextInt();
        heights = new int[studentCount];
        dp = new long[1 << studentCount][studentCount];

        for (int idx = 0; idx < studentCount; idx++) {
            heights[idx] = scanner.nextInt();
            dp[1 << idx][idx] = 1;
        }
    }

    /*
     * 브루트포스 알고리즘으로 풀기에는 시간 초과가 발생한다
     * 그러므로 이전의 결과를 이용하여 다음 결과를 구해야한다
     * 한 자리에 어떤 학생이 설지는 바로 이전 사람과 K보다 큰 키 차이가 나야한다
     * 그리고 바로 이전 사람 그 전에 서있는 사람들은 어떤 순서로 서있든 결국 같은 학생들이 서있다면
     * 그 다음에 올 수 있는 경우의 수는 모두 같다
     * 그렇기 때문에 dp 배열을 현재까지 선 학생들을 비트로 표현한 수와 각 학생을 기준으로 만든다
     *  - dp[state][student] = student 학생이 마지막으로 서있고, 현재까지 state 상태처럼 학생들이 서있을 때 배열의 경우의 수
     *      - state는 아래와 같이 설정한다
     *          - 예를 들어 4명의 학생이 있고, 1, 3번이 서있는 상황이라면 state 값은 0101 = 5가 된다
     * 각 상태에서 각 학생들을 마지막으로 세웠을 때 그 다음 올 수 있는 학생들을 세워보며 경우의 수를 늘려간다
     */
    static void solution() {
        findNumberOfCases();
        System.out.println(calculateTotalNumberOfCases());
    }

    static long calculateTotalNumberOfCases() {
        long answer = 0;
        int state = (1 << studentCount) - 1;
        for (int idx = 0; idx < studentCount; idx++) {
            answer += dp[state][idx];
        }

        return answer;
    }

    static void findNumberOfCases() {
        for (int state = 1; state < (1 << studentCount); state++) { // 현재 상태를 나타내는 변수를 이용하여 모든 상태를 순회한다
            for (int student = 0; student < studentCount; student++) { // 마지막에 설 학생을 1번 학생부터 마지막 학생까지로 각각 정해본다
                if (dp[state][student] == 0) { // state 상태에서 마지막 학생을 student로 했을 경우를 도달할 수 없다면 다음 학생을 마지막으로 세워본다
                    continue;
                }
                // 마지막 학생 및 상태를 정했으니 그러한 상황에서 다음 학생을 1번 학생부터 마지막 학생까지 세워본다
                // 그 중 가능한 경우는 dp[state][student]만큼의 경우의 수가 추가로 가능해지는 것이므로 dp[state][student]만큼 경우의 수를 더해준다
                for (int nextStudent = 0; nextStudent < studentCount; nextStudent++) {
                    int newState = state | (1 << nextStudent);
                    // 이전에 서지 않은 학생이고 마지막 학생과 키 차이가 K 초과로 난다면
                    // 가능한 경우이니 dp[state][student]만큼 경우의 수를 더해준다
                    if ((state & (1 << (nextStudent))) == 0
                            && Math.abs(heights[student] - heights[nextStudent]) > minDiff) {
                        dp[newState][nextStudent] += dp[state][student];
                    }
                }
            }
        }
    }

    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());
        }
    }
}