https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
풀이과정
①문제 바라보기
이 문제는 타일링문제로 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])
'Algorithm > 문제풀이' 카테고리의 다른 글
| [백준] 1912번 연속합 (Python) (0) | 2022.08.30 |
|---|---|
| [백준] 9461번 파도반 수열 (Python) (0) | 2022.08.30 |
| [백준] 9184번 신나는 함수 실행 (Python) (0) | 2022.08.30 |
| [백준] 1149번 RGB거리 (Python) (0) | 2022.08.22 |
| 미로 탈출 (0) | 2022.08.05 |