백준 15717번: 떡파이어

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

문제 풀이

수학

mod = $10^9 + 7$

res = $2^{N - 1}$을 $10^9 + 7$로 나눈 나머지

base = $2^{N - 1}$을 분할 정복으로 구하기 위해 현재 곱해야 하는 값

e = $2^{N - 1}$을 분할 정복으로 구하기 위해 현재 남은 지수의 값

떡국을 연속적으로 매일 먹은 총 갯수가 N개임

N개를 일렬로 나열한 이후 빈 칸에 칸막이를 두면 그 뒤에 떡국은 다음날에 먹은걸로 생각할 수 있음

N개를 일렬로 나열했으므로 빈 칸은 총 N - 1개가 되고 빈칸마다 칸막이를 놓거나 놓지 않는 2가지 선택지가 있음

총 선택지는 그러면 $2^{N - 1}$이므로 이를 $10^9 + 7$로 나눈 나머지를 구해 출력하면 됨

거듭제곱을 분할 정복으로 구하기 위해 지수를 e, 곱해야 하는 밑을 base, 결과를 저장할 변수를 res로 정의함

거듭제곱의 지수를 이진수로 나타내면 지수 법칙에 따라 이진수에서 1이 되도록 하는 지수들의 합으로 나타낼 수 있음

이에 따라 매번 base를 제곱해 매번 이진수의 다음 자릿수의 거듭제곱으로 만들고 e를 2로 나눴을 때 홀수일때만 해당 자릿수가 1인 것이므로 그때마다 res에 base를 더해 mod로 나누면 됨

그렇게 하면 res에 $2^{N - 1}$을 $10^9 + 7$로 나눈 나머지가 저장되므로 출력하면 정답

풀이 설명

떡파이어는 떡국을 먹은 그릇 수만큼 나이를 먹고 하루에 떡국을 제한 없이 먹을 수 있으며 떡국을 하루라도 먹지 않으면 생을 마감한다고 했을 때 N세로 생을 마감한 떡파이어가 나이를 먹는 경우의 수를 구하는 문제이다.

떡국을 평생 N 그릇을 먹는 것이고 연속적으로 매일 먹어야 하므로 떡국 N 그릇을 일렬로 세워놓고 사이에 칸막이를 두면 그 칸막이 뒤에 있는 떡국들은 다음 날에 먹는다고 생각할 수 있다.

이에 따라 생각해보면 N개의 그릇 사이에 칸막이를 놓을 수 있는 빈 칸이 N - 1개 있는 것이므로 각 빈 칸마다 칸막이를 놓거나 놓지 않는다는 선택지가 있으므로 전체 선택지는 $2^{N - 1}$가지가 된다.

다만 N이 0일때는 떡국을 먹지 않는다는 선택지만 있으므로 1을 예외적으로 출력하도록 처리해야 한다. 이는 거듭제곱을 구할 때 지수가 1 이상일때만 곱해주도록 처리하면 처리할 수 있다.

이에 따라 N이 주어지면 $2^{N - 1}$를 구해서 출력하면 되는데 가짓수가 많을 수 있으므로 $10^9 + 7$로 나눈 나머지를 구해야 한다.

또한 N이 최대 $10^{12}$라고 했으므로 그냥 곱해서 구할 수는 없다. 그러므로 거듭제곱을 분할 정복을 이용해 구해야 한다.

지수 법칙에 따라 지수가 합의 형태로 나뉠 수 있으므로 거듭제곱을 절반으로 계속 분해해서 곱할 수 있다. 이에 따라 지수를 이진수로 나타내 1이 될때만 해당 지수의 거듭제곱을 곱해주는 방식을 사용하면 분할 정복으로 빠르게 거듭제곱을 구할 수 있다.

이에 따라 결과를 저장할 변수 res, 구해야 하는 지수를 e, 해당 자릿수에 곱해야 하는 값 base로 정의하고 매번 e를 2로 나누고 base를 제곱하면서 홀수인지 확인해 홀수일때만 base를 res에 곱해주면 거듭제곱을 구할 수 있다.

이때 $10^9 + 7$로 나눈 나머지를 구해야 한다고 했으므로 나머지의 성질에 따라 매번 값을 곱할때마다 이 값을 mod에 저장하고 나눈 나머지를 저장하면 된다.

계산을 하면 res에 최종적으로 구하는 값인 $2^{N - 1}$을 $10^9 + 7$로 나눈 나머지가 저장되므로 출력해주면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    nextToken()
    val N = nval.toLong()
    val mod = 1_000_000_007
    var res = 1L
    var base = 2L
    var e = N - 1
    while(e > 0){
        if(e % 2 == 1L){
            res = (res * base) % mod
        }
        base = (base * base) % mod
        e /= 2
    }
    println(res)
}