[SWEA 문제해결 기본: Stack] [Python] 4869.종이접기

문제

• SWEA Stack 4869 D2
• 파이썬
• 문제링크

SW Expert Academy

접근

이 문제는 점화식을 사용해서 푸는 문제라고 한다..! 처음 문제를 보았을 때 대체 어떻게 접근을 해야하는지 몰라서 여러 코드를 찾아봤는데 아직도 잘 이해가 가지 않기 때문에 다음에 리뷰해보겠다 ㅠㅠ 동적프로그래밍(Dynamic Programming)의 일종이라고도 한다.

방식: n  = 1, n = 2, n = 3 ... 일 때의 경우의 수를 찾아본다. n = 1 일 때는 경우가 1개가 나오고 n = 2일 때는 경우가 3개가 나온다. n = 3일 때부터 규칙이 드러나는데 그 규칙을 dp(n-1) + 2 * (dp(n - 2)) 라고 정의했다.

나의 코드 (찾아본 코드)

def dp(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    return dp(n - 1) + 2 * (dp(n - 2))

T = int(input())
for i in range(T):
    N = int(input())
    print('#' + str(i + 1) + ' ' + str(dp(n//10)))