[프로그래머스] 2 x n 타일링 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제를 처음에 모든 경우마다 팩토리얼로 총경우의 수를 구했는데 시간초과 문제가 발생하였다.

하여 이전 결과를 활용하는 DP 알고리즘으로 해결하였다.

처음 n이 0일 때는 1가지, 1일 때는 1가지이다.

다음 n이 2일 때는 2가지, 3일 때는 3가지, 4일 때는 5가지로 증가한다.

결과를 나열해 보면 1-1-2-3-5-... 의 결과가 나오는데 이를 자세히 보면 다음 결과는 이전 결과와 그전 결과를 더한 결과가 된다. 1, 1, 1+1=2, 1+2=3, 2+3=5의 결과로 계속 이어진다.

이를 DP로 해결하면 답을 쉽게 구할 수 있다.

 

1. 처음 n이 0일 때 결과를 저장한다. count1 = 1
2. n이 1일 때의 결과도 저장한다. count2 = 1
3. 다음 n이 2일 때부터 n까지 반복하며 for i in range(2, n + 1)
4. 다음 결과는 이전 결과와 그전 결과를 더한 값이다. count = count1 + count2
5. 다음 결과를 구했다면 이전 결과와 그전 결과를 하나씩 앞의 결과로 옮긴다. count1 = count2  count2 = count
6. 마지막에 n일 때의 결과를 1,000,000,007로 나눈 나머지를 저장한다. answer = count % 1000000007

반응형

3. 소스코드

def solution(n):
    answer = 0
    
    count1 = 1
    count2 = 1
    for i in range(2, n + 1):
        count = count1 + count2
        count1 = count2
        count2 = count
        
    answer = count % 1000000007
    
    return answer