백준 25345번: 루나의 게임 세팅

문제: https://www.acmicpc.net/problem/25345

문제 풀이

수학, DP

mod = $10^9 + 7$

comb[i][j] = i개의 수에서 j개의 수를 뽑는 경우의 수를 mod로 나눈 나머지

base = 거듭제곱을 이진수를 이용한 분할 정복으로 구할 때 현재 상태에서 곱해야 하는 수

e = 거듭제곱을 이진수를 이용한 분할 정복으로 구할 때 현재 상태에서 남은 지수

result = 이진수를 이용한 분할 정복으로 구한 $2^{K - 1}$

타워 N개에서 K개를 고르는 것이므로 N개에서 K개를 뽑는 조합을 구해야 함

파스칼의 삼각형을 이용해 DP로 조합을 구할 수 있음

comb[i][j]를 i개의 수에서 j개의 수를 뽑는 경우의 수로 정의하고 comb[N][K]를 구함

K개의 타워를 앞, 뒤에서 볼때 최소한 모든 타워가 한번 보이는 것은 앞에서 보이는 타워는 오름차순으로 정렬, 뒤에서 보는 타워들은 내림차순으로 정렬된 것을 나타냄

따라서 서로 높이가 다른 K개의 타워 중 가장 높이가 높은 타워를 기준으로 나머지 K - 1개의 타워를 높이가 높은 순으로 앞에 놓거나 뒤에 놓으면 자동적으로 높이가 가장 높은 타워를 기준으로 앞은 오름차순, 뒤는 내림차순이 됨

이 경우 K - 1개의 타워마다 앞, 뒤라는 2가지 선택지가 있으므로 경우의 수를 계산하면 $2^{K - 1}$이 됨

거듭제곱은 지수 법칙에 따라 지수가 합으로 나타날 수 있기 때문에 이진수를 이용한 분할 정복으로 $2^{K - 1}$을 구함

구한 comb[N][K]에 $2^{K - 1}$를 곱하고 mod로 나눈 값을 출력하면 정답

풀이 설명

서로 다른 높이의 타워 N개가 있을 때 K개를 골라서 앞, 뒤에서 볼때 최소한 모든 타워가 한번은 보이도록 정렬하는 경우의 수를 구하는 문제이다.

먼저 N개에서 K개를 고르는 경우는 조합으로 구할 수 있다. K개를 앞, 뒤에서 볼때 최소한 모든 타워가 한번은 보이도록 정렬한다는 것은 앞에서 볼때 보이는 타워는 오름차순, 뒤에서 볼때 보이는 타워가 내림차순으로 정렬되어야 한다는 것으로 가장 높은 타워를 기준으로 앞에는 오름차순, 뒤에는 내림차순으로 정렬되어야 한다는 것이다.

이때 모든 타워의 높이가 서로 다르다고 했으므로 고른 K개의 타워 중 가장 높은 타워를 기준으로 두고 K - 1개의 타워를 현재 배치된 타워의 앞 또는 뒤에 배치하면 자연스럽게 가장 높은 타워를 기준으로 앞은 오름차순, 뒤는 내림차순의 순서로 정렬되게 된다.

그렇게 K - 1개의 타워가 각각 2가지 선택지가 있으므로 정렬하는 경우의 수는 $2^{K - 1}$이 된다. 그러므로 여기에 N개의 타워에서 K개의 타워를 뽑는 경우의 수 $\binom{N}{K}$를 곱해주면 구하는 경우의 수가 된다.

N개에서 K개를 고르는 것은 다음과 같이 나타낼 수 있다. 1개를 먼저 골라놓고 N - 1개에서 K - 1개를 고르는 경우, 앞에 먼저 골라놨던 1개를 제외한 N - 1개에서 K개를 고르는 경우가 있다.

이는 결국 N - 1개에서 K - 1개, K개를 고르는 경우로 나뉘기 때문에 조합을 DP로 구할 수 있다.

따라서 comb[i][j]를 i개에서 j개를 뽑는 경우의 수로 정의하고 comb[0][0]이 0개에서 0개를 뽑는 것이므로 이를 1로 초기화하고 i를 점점 키우며 comb[N][K]를 구하면 원하는 N개에서 K개를 뽑는 경우의 수를 구할 수 있다.

그 이후엔 $2^{K - 1}$을 구해야 하는데 이는 지수 법칙에 따라 지수가 합으로 나뉘는 성질을 이용해 지수를 이진수로 나타내는 방식으로 분할 정복의 방법으로 구할 수 있다. 예를 들어 $2^{13}$을 구할 때 13을 이진수($1101_2$)로 생각하여 $2^8 \times 2^4 \times 2^1$로 나누어 계산함으로써, 연산 횟수를 $O(K)$에서 $O(\log K)$로 획기적으로 줄일 수 있다.

이런 방법으로 구한 comb[N][K]에 $2^{K - 1}$을 곱한 값에 $10^9 + 7$로 나눈 나머지를 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run{
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val K = nextInt()
    val mod = 1_000_000_007
    val comb = Array(N + 1){IntArray(N + 1)}
    comb[0][0] = 1
    for(i in 1..N){
        comb[i][0] = 1
        for(j in 1..i){
            comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod
        }
    }
    var base = 2L
    var e = K - 1
    var result = 1L
    while(e > 0){
        if(e % 2 == 1){
            result = result * base % mod
        }
        base = (base * base) % mod
        e /= 2
    }
    println(result * comb[N][K] % mod)
}