[Python] 1904번 01타일, 자세한 설명, 그림 참조

✏️ 문제

 

문제 파악

n이 1, 2, 3, 4일 때 각각 dp[n]의 값을 구하면 쉽게 점화식을 구할 수 있다. 

그림을 그려보면 다음과 같다.

하지만 이 문제는 메모리가 적고 시간이 매우 짧다는 점..!

고민해보니 3개짜리 배열만 사용하면 되는 거 같아서 인덱스로 들어올 값을 %3 해 인덱스로 써서 풀었다.

 

그리고 이 문제는 답에 15746으로 나눈 값을 구하고 있다.

처음엔 마지막 print에서 % 15746 했었는데 시간 초과가 떠서 애초에 배열에 값을 넣을 때 % 15746을 하니 풀렸다!

 

 

알고리즘

• 다이나믹 프로그래밍 

 

코드

n = int(input())
dp = [1, 2, 3]

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

print(dp[(n-1) % 3])