[ 프로그래머스 ] 2 x N 타일 파이썬python 풀이

 

//문제요약

 

1x2 짜리 타일을 이용해서

 

2xn 짜리 바닥을 모두 채우는

 

모든 경우의 수를 구해라.

 

단, 경우의 수가 매우 클 수 있으므로

 

1000000007 로 나눈 나머지를 반환해라.

 

 

//풀이

 

한 시간 반을 씨름했는데 다른 사람 풀이 보고 

 

너무 어이가 없게 풀려 버려서 기운이 쭉 빠지는 문제였다.

 

코드부터 보면

 

def solution(n):
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = (a + b) % 1000000007, a
    return a

끝이다.

 

나는 처음에

 

주어진n에대해서2로나눈몫과나머지를구한다음2의수와1의수를더한값의팩토리얼을2의수의팩토리얼과1의수의팩토리얼로나눈다음이걸2의수가0이될때까지줄이면서2의수가하나줄때마다1의수를2개늘려가면서구했는데이게너무숫자가크고오래걸리니까n팩토리얼까지미리모두구한다음prefix_sum알고리즘을사용해서불러오고....

 

이런 접근과 작업이 모두 허사였다...

 

왜 이런 생각의 늪에 빠졌는고 하니

 

주어진 함수는 n에 대한 의존성을 가지는데

 

나는 n이 주어지면 그 안에서 논리를 전개하려고 하니까

 

n의 변화에 따른 더 쉬운 규칙을 발견하지 못 한 것이다.

 

알고리즘 문제를 푸는데 팩토리얼이 무슨 말이냐....

 

 

이걸 n의 변화에 따라서 나타내보면

 

n의 값	가능한 모든 조합	경우의 수
1	1	1
2	11, 2	2
3	111, 12, 21	3
4	1111, 112, 121, 211, 22	5
5	11111, 1112, 1121, 1211, 2111, 122, 212, 221	8

 

이고 여기까지만 봐도 경우의 수가

 

피보나치 수열을 나타내고 있음을 귀납적으로 알 수 있다.

 

따라서 다른 풀이들로는 적어도 O(2n) 의 시간이 필요한데 반에

 

이 동적프로그래밍 방식은 무조건 O(n) 안에 끝난다고 볼 수 있다.

 

내가 구현해야하는 함수가 어떤 의존성을 가지고 출력의 경향을 만들어내는지

 

그것에 집중하면서 풀이하면 조금 더 좋은 개발자가 될 수 있을 것이다.