날짜: 2022년 12월 30일
카테고리: 다이나믹 프로그래밍
태그: silver.3, 1904, 파이썬

백준 1904 - 01타일

입출력 예시

내가 적은 코드

N = int(input())

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for i in range(3,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%15746

print(dp[N])

풀이 과정

기본적인 DP 문제 중 하나
규칙을 잘 찾아본다면 중복되는 작은 문제들의 반복됨을 찾을 수 있다.
다만, 마지막에 15746을 나눠주게된다면 메모리 초과가 일어날 수 있어서 연산 중간중간 그때그때 15746으로 나누어주어야 한다.

리뷰

• 베스트코드들은 효율적인 측면에서는 나보다 효율적인 코드인데 가독성적인 면에서 떨어져서 굳이 첨부하지 않았다.
• 비트마스크로 푼 알고리즘 굇수들도 있던데 DP 문제를 풀며 감을 익히려는 지금의 나에게는 크게 의미없는 코드인듯 했다.