백준 31537번: 출근하기 싫어 1 (Python)

문제링크

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

문제 총평

- 조합론을 몰라도 풀 수 있는 플레티넘 문제

문제 접근방식

- 총 N명의 직원이 있는데, 이 중 최대 1명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만  1명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.

- 이 구절만 봐도 문제를 풀 수 있습니다.

- 예를 들어 첫 번째 입력을 보겠습니다.

- 총 4시간의 근무 시간 중 두명다 3시간은 근무를 해야합니다 -> 즉 각각은 1시간 씩은 쉬어야 합니다.

- 즉 정답은 이 경우의 수의 곱이 됩니다.

- 이 관점에서 문제의 풀이는 N명이 각각 쉬어야 하는 시간을 구하여 m에서 어느 시간대에서 쉬어야 하는지를 파악하면 됩니다.

- 단 문제 조건상 m이 백만 이기 때문에 DP를 이용하여 미리 팩토리얼을 구해주어서 사용하면 훨씬 빠르게 답을 구할 수 있습니다.

- 그 방법은 먼저 정답을 m! 으로 둔 뒤 각각 쉬는 시간의 팩토리얼을 계속 나눠주는 겁니다.

- 그리고 마지막으로 m - 총 쉬는시간을 나눠주고 mod 연산을 해주면 답이 나옵니다.

- 여기서 마지막 2!를 나눠주는 이유는 실제로는 정답에는 포함되지 않는 2C2가 포함되어 있기 때문에 정답을 구할때는 일부러 나눠주는 것 입니다.

- 고수분 중에서 Multinomial 유형이라고 알려주어서 관심 있으신분들은 찾아보시면 좋을거 같습니다.

 

 

정답코드 

import sys; input = sys.stdin.readline
n,m = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
    arr[i] = (m - arr[i])
if sum(arr) > m:
    print(0)
    exit()
mod = int(1e9) + 7
nums = [1]
for i in range(1,m+1):
    nums.append(nums[-1] * i % mod)
ans = nums[m]
tem = 1
for i in arr:
    tem *= nums[i]
    tem %= mod
tem *= nums[m - sum(arr)]
tem %= mod
print(ans * pow(tem, -1, mod) % mod)

 

정답코드 (완전탐색)

- 사실 실제로는 테스트케이스가 부족하여 완전탐색을 해도 정답처리는 됩니다 ㅎㅎ

import sys; input = sys.stdin.readline
n,m = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
    arr[i] = (m - arr[i])
if sum(arr) > m:
    print(0)
    exit()
ans = 1
mod = int(1e9) + 7
for i in arr:
    for j in range(i,0,-1):
        ans *= m
        m -= 1
    for j in range(i,0,-1):
        ans //= j
    ans %= mod

print(ans % mod)

 

 

문제 풀이 후 생각

- 플레티넘 치고는 쉬운 문제였습니다. 

 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요