[백준] 1904번 01타일(Python)

https://www.acmicpc.net/problem/1904

1904번: 01타일

---

풀이과정

①문제 바라보기

 이 문제는 타일링문제로 dp문제 중 하나이다. 저번에 타일링 문제를 풀었었는데 그때 점화식으로 푼 기억이 난다. 사실 dp문제가 점화식으로 많이 풀리긴 하더라..

고통을 받으며 점화식을 찾게 되었다.

dp[i] = dp[i-1] + dp[i-2] 였던 것임!

 

②아이디어 열기

신나는 마음으로 코드를 짰는데.. 나름 짧아서 예뻤다. 근데 메모리초과가 떴다!! 오마이갓..

메모리 초과 코드

사실 저 식이 피보나치잖아? 그리고 이게 메모리 초과라고 하면.. 이유가 뭘까?

 

"첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다." 라는 조건이 있네요.. 이걸 추가해서 내볼까? 

또 메모리 초과!

띠용! 또 메모리 초과네요.

메모리 초과의 근본적인 원인이 무엇일까요? 값이 크기 때문입니다.

믿음을 갖고 이번에는 계속 계속 나누도록 만들었습니다. 그럼 저장할 값이 커질 염려는 없지요.

띠용 런타임에러

런타임 에러가 뜨네요.. 이건 Range 문제일거같음.

역시 문제가 맞았다. 1을 넣을 경우 Out of range 됨

이제 해결!!

해결했습니다.

N = int(input())
dp = [0]*(N+1)
if N == 1:
    print(1)
    exit()
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])