[백준/19587] 객실 배치 (Python)

Problem : https://www.acmicpc.net/problem/19587

19587번: 객실 배치

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:14:35

 

---

 

문제 설명

 

성민이는 한 층에 2개의 객실이 있는 N층짜리 호텔을 운영하고 있다. (물리적으로 어떻게 가능한지는 무시하도록 하자)

각 호실은 자연수 번호를 가지고 있으며, 100으로 나눈 몫은 층수를 나타내고, 나머지는 1 또는 2이다. 한 층에 있는 두 방은 나머지가 서로 다르다. 나머지가 같으면서 몫이 1 차이 나는 두 방은 위아래로 인접하게 배치되어 있다. 예를 들어 1층에는 101호실과 102호실, 2층에는 201호실과 202호실이 존재한다.

어느 날 정부에서 전염병의 악화로 인한 “사회적 거리두기”를 선포하면서, 성민이는 호텔에 투숙하려는 고객들을 안내할 때 좀 더 경각심을 두고 조심스럽게 안내해야 한다.

호텔에서 객실을 배정할 때, 아래와 같은 조건들을 고려해야 한다.

 

1. 사회적 거리를 두기 위해, 같은 층에 고객을 동시에 배치하면 안 된다. 예를 들어 101호와 102호에 동시에 고객을 배치할 수 없다.
2. 전염병은 공기를 통해 퍼질 수 있기 때문에, 고객을 위아래로 인접하게 배치하면 안 된다. 예를 들어 101호와 201호에 동시에 고객을 배치할 수 없다.

N층의 호텔을 운영하는 성민이가 고객을 배치할 수 있는 경우의 수는 몇 가지일까?

 

입력 및 출력

 

입력

 

성민이가 운영하는 호텔의 층수인 정수 N이 입력으로 주어진다. (1 ≤ N ≤ 10^18)

 

출력

 

성민이가 객실에 고객을 배치할 수 있는 경우의 수를 109 + 7로 나눈 나머지를 출력한다.

 

입력 예시

 

1

 

출력 예시

 

3

 

 

---

 

풀이

 

DP 문제. 그런데 분할정복 거듭제곱 개념을 곁들인.

 

우선 n01번 방에 배치하는 경우를 an, n02번방에 배치하는 경우를 bn, 두 방 모두 배치하지 않는 경우를 cn이라고 두자. 다음이 성립한다.

 

단순히 DP로 이를 계산할 수는 있겠으나, O(N)시간복잡도가 소요된다. N이 최대 10^18이므로 이 방법을 더 효율적으로 계산해야 한다.

 

우리가 궁금한 값은 N번째 방을 배치하는 경우의 수의 합이다. 또한, 두 방 모두 배치하지 않는 경우를 따로 두어 생각해 보자. 다음 수식으로 정리해 볼 수 있겠다.

 

n+1번째를 나타내면 다음과 같아진다.

 

즉 이를 행렬식으로 나타내 볼 수 있겠다!

 

f(0) = 1, f(-1) = g(0) = 1이 되므로(0층에는 아무도 배치하지 않는 1가지 경우만이 존재한다) 위 식이 성립한다. 우리는 분할 정복을 통한 거듭제곱으로 행렬의 제곱을 구한 뒤, 최종적으로 이 행렬식의 연산 결과를 반환하면 되겠다.

 

풀이 코드

MOD = 10**9+7
N = int(input())
mat = [[2, 1], [1, 0]]

def matmul(a, b):
  c = [[0]*2 for _ in range(2)]
  for k in range(2) :
    for i in range(2) :
      for j in range(2) :
        c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD
  return c

def matpow(m, p) :
  if p == 1 :
    return m
  _m = matpow(m, p//2)
  _m = matmul(_m, _m)
  if p % 2 :
    _m = matmul(_m, m)
  return _m

print(sum(matpow(mat, N)[0]) % MOD)

풀이 완료!