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