[파이썬]백준 1904 01타일

링크

백준 1904 01타일

오늘 삼성 모의 A형 문제를 풀면서 DP의 벽을 다시한번 씨게 느꼈다..
분명 잠시 손 놓기 전엔 DP를 잘 풀수있다고 생각했는데 너무 건방진 생각이었다.
기초부터 다시 차근차근 쌓아야할 필요를 느꼈다.

해당 문제는 문제 자체는 굉장히 쉬웠으나 파이썬을 사용하며 메모리에대해 생각해 본적 없던것이 뽀록났다.
점화식에 맞게 memoization을 하고 마지막에 원하는 숫자를 15746 으로나눈 나머지를 구했는데 입력값이 조금만 커져도 수가 걷잡을 수 없이 커져 안돌아 가는 것은 물론이고 컴터가 다운돼버렸다..

memoization 전에 미리 %15746 을 해주고 적어주어서 풀 수 있었다.

정답 코드

N = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
if N == 1:
    print(dp[1])
elif N == 2:
    print(dp[2])
else:
    for i in range(3, N + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
    print(dp[N])

알게된 것👨‍💻

• 연산 순서를 통해 메모리를 절약할 수 있다.