백준 11726번 파이썬 문제풀이(DP - 2*n 타일링)

---

입력 N	1	2	3	4	5	6
방법의 수	1	2	3	5	8	13

이 문제는 간단하게 첫번째 항과 2번째 항의 값이 3번째 항의 값과 같다 라는 점화식만 잘 찾으면 된다. 사실 타일에 들어가는 구성을 보고 이 점화식을 찾아야하는데 사실 dp문제라는걸 몰랐다면 이걸 찾는데 오래 걸릴꺼 같다는 생각을 했다. 

 

코드1 (반복문 돌기전 미리 dp리스트를 n+1개 만큼 초기화)

n = int(input())

dp = [0, 1, 2]  # n이 2이하일때 횟수를 미리 초기화
if n > 2:  # 만약 n이 3보다 크다면
    dp = dp + ([0] * (n - 2))  # 반복문을 돌기 위해 그 이후의 n-2개를 dp배열에 추가해준다.
    for i in range(3, n + 1):  # 3 부터 n 까지 점화식을 돈다.
        dp[i] = dp[i - 1] + dp[i - 2]  # 3번째 항부터 1,2번째 항의 합과 같다. (i번째 항은 i-2번째항과 i-1번째 항의 값과 같다.)

print(dp[n] % 10007)  # 출력

 

코드2 (append 이용)

n = int(input())

dp = [0, 1, 2]
if n > 2:
    for i in range(3, n + 1):
        dp.append(i)
        dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n] % 10007)

-> 위와 거의 동일한 코드인데 미리 dp를 n+1개 만큼 정의해놓지 않고 반복문을 돌면서 dp 배열에 append함수로 i번째 값을 넣어봤는데 append메서드가 사실 시간복잡도를 꽤 잡아먹는 메서드로 알고 있는데 n의 범위가 작아서 인지 크게 차이는 나지 않았다.

 

-> 72ms 가 append를 이용한 점화식