백준 1904 - 01타일

문제

알고리즘 분류)

• 다이나믹 프로그래밍

풀이

백준 dp알고리즘에 나와있는 문제이다
메모이제이션으로 미리 배열을 충분히 만들어 놓고
알맞은 점화식으로 N번째 배열을 N-i , N-j 등으로 채워나가면 되는 문제로 '파도반수열' 문제와 비슷하다
N이 커질수록 정수가 엄청나게 증가하므로 미리 15746으로 나누어서 배열에 저장해야 오류가 나지않는다

소스코드

python)

array = [1,2]+[0]*999999

N = int(input())
for i in range(2,N+1):
    array[i] = (array[i-1] + array[i-2])%15746
    
print(array[N-1])