[프로그래머스/Lv2] 2 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

 

 

코드

def solution(n):
    if n < 3:
        return n
    
    cache = [0 for _ in range(n+1)]
    cache[0] = 1
    cache[1] = 2

    for i in range(2, n):
        cache[i] = (cache[i-1] + cache[i-2]) % 1000000007
    
    return cache[n-1]

 

 

설명

결론부터 말하자면 이 문제는 피보나치 수열 문제와 똑같다.

문제를 풀면서 시간초과에 주의만하면 된다.

 

왜 피보나치 수열과 똑같은지는 그림과 같이 설명하겠다.

 

f(1)

n=1 일때 타일을 채우는 방법은 한가지 밖에 없다. (f(1) = 1)

 

f(2)

n=2 일때 타일을 채우는 방법은 두가지가 있다. (f(2) = 2)

 

이제 n이 3일때부터를 살펴보자.

 

f(3)

n=3 일때 타일을 채우는 방법은 세가지가 있다.

여기서 첫번째 타일이 세로로 들어갔을 때를 생각해보자.

가로의 길이 3 중에 1이 채워졌으니 우리는 이제 나머지 2를 타일로 채워야 할 것이다.

그런데 우리는 이미 가로 길이 2인 바닥을 타일로 채우는 경우의 수를 구해놨다(f(2) = 2).

 

마찬가지로 첫번째 타일이 가로로 들어갔을 때를 생각해보자.

가로의 길이 3 중에 2가 채워졌으니 나머지 1을 타일로 채워야 한다.

우리는 또 이미 가로 길이 1인 바닥을 타일로 채우는 경우의 수를 구해놨다(f(1) = 1).

 

즉, (가로의 길이가 3인 바닥의 타일을 채우는 경우의 수)는 (가로의 길이가 2인 바닥의 타일을 채우는 경우의 수)와 (가로의 길이가 1인 바닥의 타일을 채우는 경우의 수)를 더한 값과 같게 된다.

f(3) = f(3-1) + f(3-2)와 같다는 뜻이다.

 

그렇다면 n=4 일때도 살펴보자.

우리가 위에서 생각한대로라면 f(4) = f(4-1) + f(4-2) = 3+2 = 5일 것이다.

 

f(4)

우리가 생각한대로 f(4) = 5가 맞았다.

 

그렇다면 이 식을 일반화하여 표현해보자.

f(n) = f(n-1) + f(n-2) (단, f(1) = 1, f(2) = 2)

이렇게 식이 일반화 된다.

 

이제 우리는 일반화된 식을 코드로 구현하기만 하면 된다.

앞에서 말했듯이 시간초과를 주의해야 하기 때문에 동적계획법을 사용해서 문제를 풀 것이다.

 

if n < 3:
    return n

함수에 2 이하의 수가 입력되면 그대로 그 수를 반환한다.

 

cache = [0 for _ in range(n+1)]
cache[0] = 1
cache[1] = 2

cache에 n+1 길이만큼 0을 초기화해준다.

cache[0]과 cache[1]을 각각 1과 2로 초기화해준다.

cache[0]과 cache[1]은 f(1)과 f(2)를 저장해둔 원소이다.

 

for i in range(2, n):
    cache[i] = (cache[i-1] + cache[i-2]) % 1000000007

2부터 n까지 cache[i]에 대한 연산을 반복한다.

f(n) = f(n-1) + f(n-2)를 식으로 표현한 것이다.

 

여기서 문제의 마지막에 나눠야할 1000000007을 지금 나눠줄 건데

원하는 값을 구한 뒤에 1000000007을 나눈 나머지 값을 반환하도록 하면 시간초과로 문제를 통과하지 못한다.

 

계산 중간중간 갱신되는 새로운 cache[n]의 값이 너무 커지면

연산할 때 시간이 많이 필요해서 그런 듯하다.

통과한 코드로 채점해보면 마지막 효율성 테스트케이스에서 12.75ms가 기록되는데

이 문제의 효율성 체크 기준이 빡빡한 탓에 연산하는 수의 크기조차 컨트롤해야하는 것이라고 생각한다.

내가 이렇게 생각하는거지 정확한 이유는 아니다.

프로그래머스 질문 탭에는 오버플로우를 예방하기 위해라는 답변도 있었다.

 

return cache[n-1]

cache[n-1]을 반환해준다.

처음부터 cache[0]에 f(1)을 cache[1]에 f(2)를 저장해뒀기 때문에

우리가 원하는 f(n)도 cache[n-1]에 저장되어 있다는 점을 까먹으면 안된다.