프로그래머스 - 2xn타일링 (파이썬)

1. 조합사용(x)

가능한 경우의 수를 조합을 사용해서 풀어보았다. nCr을 풀기위해 nPr/r!을 만들었는데 n이 일정값 이상이 되면 nPr이 int형 범위를 벗어나 오버플로우 현상이 발생함을 확인했다.

 

def comb_len(n,r):
    top,bottom=1,1
    if n-r<r:
        r=n-r
    if r==0:
        return 1
    for i in range(n,n-r,-1):
        top*=i
    for i in range(r,0,-1):
        bottom*=i
    return top//bottom

def solution(n):
    answer = 0
    one_len=n
    while(one_len>=0):
        answer+=(comb_len(n,one_len))
        n-=1
        one_len-=2
    return answer

 

 

2. 피보나치수열 사용(dp)

n값을 1부터 5까지 설정하여 answer을 구해보았다

n=1  ->  answer=1

n=2  ->  answer=2

n=3  ->  answer=3

n=4  ->  answer=5 

n=5  ->  answer=8

피보나치 수열을 이루므로 n이 3 이상일 때 앞에 두 값을 더해서 구해주었다.

 

def solution(n):
    arr=[0]*(n+1)
    arr[1]=1
    arr[2]=2
    if n==1:
        return 1
    if n==2:
        return 2
    for i in range(3,n+1):
        arr[i]=(arr[i-1]+arr[i-2])%1000000007 #오버플로우 방지
    return arr[n]