[4코1파] #80. LV 2. 2 x n 타일링

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (80일차)
[4코1파] 2023.01.13~ (71일차)

Today :

2023.03.24 [80일차]

프로그래머스 LV 2
2 x n 타일링
https://school.programmers.co.kr/learn/courses/30/lessons/12900

문제 설명

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

제한사항

가로의 길이 n은 60,000이하의 자연수 입니다.
경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

입출력 예 설명
입출력 예 #1
다음과 같이 5가지 방법이 있다.

문제 풀이 방법

동적계획법 dp 로 풀었고,
n=1 일때 1
n=2 일때 2
n=3 일때 3
n=4 일때 5
n=5 일때 8

요런식으로 함수식이 dp[n] = dp[n-1] + dp[n-2] 여서,
그대로 했다가는 메모리 난리나서
바로바로 1000000007 를 나눠준 값을 리스트에 넣어서 해결

내 코드

def solution(n):
    
    dp = [_ for _ in range(n)]
    dp[0], dp[1] = 1,2
    
    for i in range(2, n):
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

        
    return dp[n-1]

증빙

다른 사람 풀이

뭔 for 문을 돌면서, a,b를 swap 하면서 해결했는데... 나이거 이해 안됨.. 도라뻐림

여담

이런 부류들의 제목을 가지고 있는건 다른 사람 풀이 보면 수학자가 따로없어