백준 1904번 - 01타일

00과 1 타일을 가지고 만들 수 있는 모든 타일 조합을 구하시오.

# 정답 코드

dp문제를 피보나치 빼고 처음 풀어본다. 처음 문제를 보고 생각했을 때 너무 어지러웠다.
경우의 수가 너무 많은거 아닌가? 규칙성이 안보이는데? 00의 위치, 개수가 계속 달라지네?
문제푸는 방법이 필요하다. 정리해보자.

1. N = 3 인 경우까지 그림을 그려 상황을 파악한다.
2. 임의의 n에 대한 값을 구한다고 가정하고 주어진 선택지만이 존재하는 상황을 만든다.
3. 점화식을 세운다.

나름 정리해봤는데 꽤 효과적이였다.

import sys
input = sys.stdin.readline

N = int(input())
d = [0 for i in range(1000001)]
d[1] = 1
d[2] = 2

# n-1개 타일을 놓고 1개(1) 추가
# n-2개를 놓고 2개(00) 추가 
# (11)의 경우도 2개를 놓을 수 있지만 n-1의 경우에서 카운트하기 때문에 고려하지 않는다.

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

# 참고 코드

정답이긴 하지만 비정상적으로 메모리도 많이 잡아먹고 시간도 오래걸린다. N의 범위가 너무 크므로 d를 안쓰고 변수 하나로 돌려쓰는 방법이 있다.

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)

이것까진 이해가 된다. 피보나치와 원리가 같으므로 뒤의 계산값과 바꿔 대입한다.
이것보다 더 엄청난 방법이 있다. 행렬의 멱법이라고 들어봤나?

# 행렬의 멱법

행렬 멱법은 점화식을 행렬화 시켜서 푸는 방법이다.

행렬의 거듭제곱을 이용하면 우선 시간 복잡도를 O(logN)으로 맞출 수 있다.
N까지 계산하지 않고(O(N)), 절반씩 줄여가면서 계산한다.
이 기법은 정확히 이해한 건 아니라서 좀 더 알아봐야 응용할 수 있을 것 같다. 지금은 이런 방식도 있다라고만 이해하고 넘어가려고 한다.
문제푸는 방식엔 정말 다양한 방법이 있는 것 같다. 이런 거 보면 모든 사람이 다 다른 코드가 나오는 것 같다.

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])

참고 블로그