백준 29719번 브실이의 불침번 근무

 

처음에는 중복 순열을 이용해서 문제를 풀어보려고 했다.

import java.io.*;
import java.util.*;
public class Main {
    static int N,M,count;
    static int[] soldier;
    static int[] vigil;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        soldier = new int[M];
        vigil = new int[N];

        for (int i = 0; i < M; i++) {
            soldier[i] = i+1;
        }
        count = 0;
        perm(0);
        System.out.println(count%1000000007);
    }

    private static void perm(int cnt) {
        if (cnt == N) {
            for (int i : vigil) {
                if (i == 1) {
                    count++;
                    return;
                }
            }
            return;
        }
        for (int i = 0; i < M; i++) {
            vigil[cnt] = soldier[i];
            perm(cnt+1);
        }
    }
}

시간 초과...

 

어차피 브실이가 불침번을 서는지만 알면 되는데 굳이 불침번을 전부 구해볼 필요가 있을까?

불침번에 브실이가 포함되기만 한다면 카운트를 올리고, 따로 불침번 리스트는 구하지 말자!

public class Main {
    static int N,M,count;

    static final int MOD = 1000000007;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = 0;
        perm(0, false);
        System.out.println(count%MOD);
    }

    private static void perm(int cnt, boolean hasBsil) {
        if (cnt == N) {
            if (hasBsil) count++;
            return;
        }
        for (int i = 0; i < M; i++) {
            perm(cnt+1, hasBsil || i == 0);
        }
    }
}

또 시간 초과..

 

방법을 찾아보다가

이 식에 대해 알게 되었다.

1. 모든 day(날짜)에 대해 M명의 soldier(군인) 중 한 명을 배치하는 경우의 수는: M의 day 제곱
2. 브실이가 포함되지 않는 경우 -> 브실이를 빼고 경우의 수를 구하자 : M-1의 day제곱
3. 브실이가 포함되는 경우 = 모든 경우 - 브실이가 포함되지 않는 경우
4. 최종적으로

위 식이 나오게 되었고, 이를 구하기 위해 빠른 거듭 제곱 알고리즘을 사용했다.

거듭 제곱 알고리즘

1. 짝수 지수일 경우: 지수를 반으로 줄이고, 밑을 두 번 곱합니다.
2. 홀수 지수일 경우: 밑을 한 번 곱하고, 지수를 하나 줄여서 짝수로 만듭니다.

private static long pow(long base, long exp, int mod) {  // base - 밑, exponent - 제곱수...
        long result = 1;
        while (exp > 0) {
            // 홀수 지수일 경우
            if (exp % 2 == 1) {
                result = (result * base) % mod;  // base를 한 번 더 곱함
                exp--;  // 지수를 1 감소시켜 홀수를 짝수로 만듦
            }

            // 짝수 지수일 경우
            base = (base * base) % mod;  // base를 두 번 곱함
            exp /= 2;  // 지수를 반으로 줄임
        }

        return result;
    }

 

최종 코드

import java.io.*;
import java.util.*;
public class Main {
    static int day, soldier;
    static final int MOD = 1000000007;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        day = Integer.parseInt(st.nextToken());
        soldier = Integer.parseInt(st.nextToken());

        long total = pow(soldier, day, MOD); // 전체 경우의 수 - soldier의 day제곱
        long exclude = pow(soldier -1, day, MOD); // 브실이가 들어가지 않는 경우의 수 (soldier-1)의 day제곱
        long result = (total - exclude + MOD) % MOD; // 전체 경우의 수 - 브실이가 들어가지 않는 경우의 수 = 브실이가 들어가는 경우의 수

        System.out.println(result);
    }

    private static long pow(long base, long exp, int mod) {  // base - 밑, exponent - 제곱수...
        long result = 1;
        while (exp > 0) {
            // 홀수 지수일 경우
            if (exp % 2 == 1) {
                result = (result * base) % mod;  // base를 한 번 더 곱함
                exp--;  // 지수를 1 감소시켜 홀수를 짝수로 만듦
            }

            // 짝수 지수일 경우
            base = (base * base) % mod;  // base를 두 번 곱함
            exp /= 2;  // 지수를 반으로 줄임
        }

        return result;
    }
}

시간초과 안나고 성공할 수 있었다.

 

문제에 대한 수학적 접근이 중요하다는 것을 알게되었다