백준 1904 파이썬 - 01타일 - 동적 계획법, 행렬

백준 1904 파이썬

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

1904번: 01타일

해당 문제는... "00" 타일과 "1" 타일로 만들 수 있는 이진수의 가짓수를 찾는 문제입니다. 이 문제도 결국 1타일과 00타일을 이전의 타입에 붙치는 문제이므로 메모이제이션을 이용한 동적계획법으로 풀 수 있다. 그런데... 직접 손으로 숫자의 패턴을 계산해보니 피보나치 수열과 완젼 동일한 숫자의 패턴을 갖고 있었습니다. 그래서 이 문제는 행렬 멱법을 사용해서 해결할 수 있었습니다.

 

Python 풀이 1

첫번 째 풀이는 동적 계획법을 사용했습니다.

import sys
read = sys.stdin.readline

N = int(read())
cache = [0] * (N+2)
cache[1] = 1
cache[2] = 2

for i in range(3, N+1):
    cache[i] = (cache[i-1] + cache[i-2]) % 15746
print(cache[N])

• 초기 값 1, 2를 저장해두고 값을 재사용하면서 문제를 풀었습니다.

문제를 풀기는 했는데... 메모리 사용량도 높고 수행 속도가 오래 걸리길래.... 코드를 조금 수정해봤습니다.

 

 

Python 풀이 2

import sys
read = sys.stdin.readline

N = int(read())
n1 = 1
n2 = 2
res = 1 if N == 1 else 2

for i in range(3, N+1):
    res = (n1 + n2) % 15746
    n1, n2 = n2, res
print(res)

두번 째 풀이는 동적 계획법으로 풀었을 때 많이 잡아먹던 메모리를 줄이기 위해 캐시 리스트를 없애고 변수로 계속 바꿔가면서 풀도록 수정했습니다. 메모리는 2배이상 절약되었고 시간도 25% 정도 절감할 수 있었습니다.

 

 

Python 풀이 3

3번째 풀이는 행렬의 멱법을 사용했습니다.

import sys
read = sys.stdin.readline

N = int(read())
A = [[1, 1], [1, 0]]

def matrix_mult(A, B):
    temp = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                temp[i][j] += (A[i][k] * B[k][j])

    for i in range(2):
        for j in range(2):
            temp[i][j] %= 15746
    return temp

def matrix_pow(n, M):
    if n == 1:
        return M
    if n % 2 == 0:
        temp = matrix_pow(n//2, M)
        return matrix_mult(temp, temp)
    else:
        temp = matrix_pow(n-1, M)
        return matrix_mult(temp, M)

print(matrix_pow(N, A)[0][0])

 문제의 결과를 손으로 계속 풀어보니까... 피보나치와 동일하게 숫자가 증가되고 있는 것을 확인했습니다. 피보나치 수열에서 가장 빠른 효율을 얻을 수 있는 방법인 행렬의 멱법을 이용한 방법을 선택했고... 동적 계획법으로 풀었던 방법보다 80%정도 빠르게 결과를 얻을 수 있었습니다.

 

피보나치를 행렬로 푸는 방법은 아래 링크를 통해 자세한 내용을 확인할 수 있습니다.

[CS/알고리즘] - 피보나치 파이썬으로 구하는 3가지 알고리즘