문제
문제 설명
- 그림과 같은 블록들을 배치하여 3xn 타일을 채우는 점화식 문제이다.
풀이
- 프로그래머스 질문 게시판에 박지상님이 올려주신 n에 따른 새로운 블록 개수와 관련된 힌트를 활용하였다.
- 힌트
- 새로운 블록의 개수는
- i=1 => 1
- i=2 => 2
- i=3 => 5
- i=4, 7, 10, ... => 2
- i=5, 8, 11, ... => 2
- i=6, 9, 12, ... => 4
- s[n]를 새로운 블록의 개수라고 한다면 점화식 A[n]은
ex) A(4) = 1*A(3) + 2*A(2) + 5*A(1) + 2 = 1*10 + 2*3 + 5*1 + 2 = 23
- 이걸 좀 풀어서 적는다면
숫자 4부터 2, 2, 4가 반복되기 때문에 A(X+3)을 활용하여 점화식을 정리할 수 있다.
위의 A(X)에서 A(X+3)을 빼면
이것을 이제 행렬로 표현하면 다음과 같다
이제 이것을 고스란히 코드로 옮기면 된다.
mod = 1000000007
def matrix_product(arr1, arr2):
l = len(arr1)
new_arr = [[0] * l for _ in range(l)]
for i in range(l):
for j in range(l):
for k in range(l):
new_arr[i][j] += arr1[i][k] * arr2[k][j]
new_arr[i][j] %= mod
return new_arr
def matrix_product2(arr, lst):
l = len(arr)
result = [0] * l
for i in range(l):
for j in range(l):
result[i] += arr[i][j] * lst[-j-1]
result[i] %= mod
return result
def solution(n):
A = [1, 3, 10, 23, 62, 170]
if n <= 6:
return A[n-1]
arr = [[1, 2, 6, 1, 0, -1]]
for i in range(5):
lst = [0] * 6
lst[i] = 1
arr.append(lst)
mat = [row[:] for row in arr]
r_matrix = [[0] * 6 for _ in range(6)]
for i in range(6):
r_matrix[i][i] = 1
cnt = n - 3
while cnt > 0:
if cnt % 2:
r_matrix = matrix_product(r_matrix, mat)
mat = matrix_product(mat, mat)
cnt //= 2
result = matrix_product2(r_matrix, A)
return result[3]후기
- 지저분하게 끄적인 노트.. 보통 2 ~ 3 level의 문제는 아이디어 떠올리고 바로 짜면 되는데, 몇 시간이 걸린건지.. 이런 문제가 코테에 나온다면 절망적일 것 같다
- 최근에 푼 연속 부분 펄스의 합이랑 같은 3레벨인데 난이도 차이가 너무 심한 것 같다..
- 처음에 mod = 1000000007값을 1e9+7로 사용하고 있어서 왜 틀리는지 찾는데도 시간이 걸렸다.
- 요즘 문제가 어렵게 나오는건지.. 내가 오래 쉬어서 못해진건지.. 열심히 해야겠다..
