[프로그래머스] 3xn 타일링 (python)
문제 설명
Idea
풀이 방법이 직관적으로 떠오르지 않아 정의된 문제의 N 값에 따른 답안을 구하며 규칙을 찾아보기로 했습니다.
우선 2x1인 직사각형 타일을 이용하여 3xN인 바닥을 채워야 합니다.
다만, 3xN 바닥의 세로 길이가 3이기 때문에 2x1 직사각형은 반드시 누워져서 들어가는 경우가 발생합니다.
이는 N이 홀수인 경우엔 2x1 직사각형 타일을 이용하여 3xN 바닥을 채울 수 없음을 의미합니다. (아래 그림 참고)
3x3, 3x5인 바닥의 경우
위 이유로 규칙은 N이 짝수인 경우에만 찾도록 하겠습니다.
1. 규칙 찾기
N=0: 0개, 타일을 둘 수 없음
N=2: 3개, 아래 사진 참고
- N=2일 때 있었던 3개의 경우에 다시 3가지의 경우의 수들 추가.
- N=4일 때 특수한 형태의 모양 생성 (그림 맨 하단 참고)
N=8: 153개, (3*41 + {6*3+2*2} + 2*3 + 2)
N=6: 41개, (3*11 + 2*3 + 2)
- N=4일 때 있었던 경우에 다시 3가지의 경우의 수들 추가.
- N=4일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우측 참고)
> 특수한 형태의 모양은 "앞, 뒤"에 따라 다른 경우의 수를 만들 수 있습니다.
- N=6일 때 특수한 형태의 모양 생성 (그림 맨 우하단 참고)
- N=6일 때 있었던 경우에 다시 3가지의 경우의 수들 추가.
- N=6일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우상단 참고)
> 특수한 형태의 모양은 "앞, 뒤"에 따라 다른 경우의 수를 만들 수 있습니다.
- N=4일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우중단 참고)
> 특수한 형태의 모양에 대한 다른 경우의 수를 만들 수 있습니다.
- N=8일 때 특수한 형태의 모양 생성 (그림 맨 우하단 참고)
2. 규칙 정리
찾은 규칙을 정리하면 다음과 같습니다.
N=2일 때 3
N=4일 때 11 -> 3*3 + 2
N=6일 때 41 -> 3*11 + 2*3 + 2
N=8일 때 153 -> 3*41 + {6*3+2*2} + 2*3 + 2
이를 다시
N=2일 때 3
N=4일 때 11 = (3)*3 + 2
N=6일 때 41 = (11)*3 + (3)*2 + 2
N=8일 때 153 = 41*3 + {6*3+2*2} + 3*2 + 2
= 41*3 + 22 + 3*2 + 2
= (41)*3 + (11)*2 + (3)*2 + 2
규칙을 잘 찾아보면 N의 값을 구하기 위해 이전의 값들을 사용하고 있음을 발견할 수 있습니다.
즉, f(n) = f(n-2)*3 + f(n-4)*2 + ... + f(2)*2 + 2
Solution
def solution(n):
if n % 2 == 1: return 0
n //= 2
if n <= 1: return [0, 3][n]
tile = [3]
for i in range(1, n):
tile.append(tile[i-1]*3 + sum(tile[:i-1])*2 +2)
return tile[n - 1] % 1000000007
f(n) = f(n-2)*3 + f(n-4) + ... + f(2)*2 + 2 수식을 사용하면 됩니다.
f(n)을 구하기 위해선 그 전 값들을 구해야하기 때문에 tile 리스트를 생성하여 f(2), f(3), ..., f(n)일 때의 값을 계산합니다.
이 때 f(3)*2 + f(2)*2 등은 {f(3)+f(2)}*2와 동일하기 때문에 sum 값을 더한 뒤 *2를 해줍니다.
마지막으로 1000000007 나눈 나머지 값으로 반환하라는 조건이 문제에 있었기 때문에 해당 부분을 추가합니다.
Refactoring
def solution(n):
if n % 2 == 1: return 0
n //= 2
if n <= 1: return [0, 3][n]
tile = [3]
for i in range(1, n):
tile.append((tile[i-1]*3 + sum(tile[:i-1])*2 + 2) % 1000000007)
return tile[n-1]
위 Solution과 동일한 풀이 방법입니다.
다만, tile[n-1]에서 1000000007을 나누는 방식이 아닌, tile 변수에 값을 더할 때마다 1000000007을 나눠 값을 작게 만들어 계산하여 속도를 증진시킵니다.
Refactoring 01
def solution(n):
# f(N-2)*4 - f(N-4)
if n % 2 == 1: return 0
pre = cur = 1
for _ in range(n // 2):
pre, cur = cur, (4 * cur - pre) % 1000000007
return cur
f(n) = f(n-2)*3 + f(n-4) + ... + f(2)*2 + 2 수식이 아닌 다른 수식으로 계산합니다.
f(n) = f(n-2)*4 - f(n-4)
위 수식으로 진행할 경우 기존 보다 약 98% 속도가 증진됩니다. (속도 측정에 대한 정보는 깃허브를 확인해주세요)
댓글
댓글 쓰기