[백준 1904번] 01타일

# 문제

---

내 풀이 - 문제 풀이 실패, 수정 답안

n = int(input())

# dp 테이블 생성 및 초기화
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])

 

문제 접근

끝이 00일 경우와 1일 경우로 나누어 생각하면 결과적으로 피보나치 수열이 나온다.

 

생각할 점

정답률이 아주 낮진 않아서 쉬운 문제라 생각했는데, 아이디어도 잘 생각나지 않고 런타임에러에 메모리 초과까지 신경쓸 부분이 많았다. 15746으로 나누는 것도 계산할 때마다 적용해서 숫자 표현 범위를 벗어나지 않게 조정해야 하는 부분도 주목하자.