(DP) 백준 1904번 01타일

n = int(input())

arr = [0,1,2] + ([0] * (n-2))

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

print(arr[n])

간단한 알고리즘이었다. 전형적인 DP알고리즘이고 피보나치 수열과 같았다. 하지만 주의할 점은 결과 값에만 15746을 나눠주는 것이 아니라 각 배열의 값마다 나눠줘야지 메모리 초과가 발생이 되지 않는다.

좋은 웹페이지 즐겨찾기