[파이썬]백준 29719번: 브실이의 불침번 근무

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

29719번: 브실이의 불침번 근무

 

---

• 문제풀이

 

열심히 종이에 적다보니 규칙을 찾게 되었다.

∑nCr*(m-1)^(n-r)이 브실이가 근무를 하는 경우의 수임을 알게 되었다.

 

 

 

그래서  브실이가 들어가는 경우의 수를 모두 합하여 구하려고 했으나 시간초과가 걸렸다.

 

# -*- coding: utf-8 -*-
import sys
MOD = 1000000007

def calculate_sigma(N, M):
    result = 0
    combination_values = [0] * (N + 1)
    exponent_values = [0] * (N + 1)
    
    combination_values[0] = 1
    exponent_values[0] = 1
    
    for R in range(1, N + 1):
        # 조합 계산에서 나눗셈을 정수 나눗셈으로 변경
        combination_values[R] = (combination_values[R - 1] * (N - R + 1) // R)
        exponent_values[R] = (exponent_values[R - 1] * (M - 1))
    
    for R in range(1, N + 1):
        result = (result + combination_values[R] * exponent_values[N - R])
    
    # 최종 결과에서 모듈러 연산
    result %= MOD
    
    return result

N, M = map(int, sys.stdin.readline().split())

sigma_result = calculate_sigma(N, M)
sys.stdout.write(str(sigma_result % MOD) + '\n')

 

 

시간초과를 해결하기 위해서는 브실이가 근무를 투입하는 경우의 수가 아니라 브실이가 근무를 들어가지 않는 수를 구해야했다.

이는 수식으로 M^N - (M-1)^N 로 나타낼 수 있다.

---

• 코드 1

# -*- coding: utf-8 -*-


MOD = 1000000007  # 나눌 모듈러 값

# 필요한 모듈 import
import sys

# 입력 받기
N, M = map(int, sys.stdin.readline().split())

# M^N - (M-1)^N 계산
result = (pow(M, N, MOD) - pow(M - 1, N, MOD)) % MOD

# 결과 출력
sys.stdout.write(str(result) + '\n')

 

---

• 후기

규칙을 찾아 수식으로 만들어내는 과정이 재밌던 문제이다.