공부 기록장
[백준 - Python] 11726. 2xn 타일링 (DP) 본문
https://www.acmicpc.net/problem/11726
코드
n = int(input())
dp = [0] * (n+2) # (n+1) 하면 왜 런타임 에러가 나는지 ??
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i - 2] + dp[i - 1]
print(dp[n] % 10007)
이와 비슷한 타일링 문제를
이코테 책으로 DP 공부하면서 풀어봤던 기억 때문에
점화식을 구하는 것은 그렇게 어렵지 않았다.
한 가지 의문이었던 점은
DP 테이블에 값을 저장할 때,
인덱스 값이 n값이랑 같게 하기 위해서 n+1의 크기를 갖는 리스트를 선언했는데
제출에서 자꾸 런타임 에러(인덱스 에러)가 났다.
(n+2)로 제출하면 통과가 됐는데,
왜 그런 것인지에 대한 해결을 못해서 스터디원들에게 도움을 구했다.
원인은 이랬다.
dp = [0] * (n+1) 인 경우에
n이 1이 들어오면
dp 리스트의 최대 인덱스는 1이 되는데,
그 다다음 줄에서 dp[2] = 2 로 없는 인덱스에 값을 저장하려고 하기 때문에 나는 에러였다!
위와 같은 경우를 방지하기 위해서
dp 테이블을 그냥 문제에서 주어지는 최댓값 + 1의 크기로 선언을 하거나
아래의 코드와 같이
n = int(input())
dp = [0] * (n + 1)
for i in range(1, n + 1):
if i == 1:
dp[i] = 1
elif i == 2:
dp[i] = 2
else:
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
print(dp[n])
반복문 안에 조건문으로 나눠서 초기화를 해주는 방법으로 구현을 하면 된다.
'코딩 테스트 > 백준 문제 풀이' 카테고리의 다른 글
[백준 - Python] 2193. 이친수 (DP) (0) | 2024.02.15 |
---|---|
[백준 - Python] 9461. 파도반 수열 (DP) (0) | 2024.02.15 |
[백준 - Python] 1003. 피보나치 함수 (DP) (0) | 2024.02.10 |
[백준 - Python] 9095. 1, 2, 3 더하기 (DP) (0) | 2024.02.10 |
[백준 - Python] 1463. 1로 만들기 (DP) (0) | 2024.02.10 |