[백준] 1904번 01타일 파이썬 해설

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

1904번: 01타일

 

DP문제의 가장 기본적인 "타일" 문제를 정리해보자!

DP에 대한 정의는 나름 여기에 정리해두었다.

 

풀이

---

문제의 특징을 잘 정리한 후 그대로 적용하면

아주 쉽게 식을 도출해 낼 수 있다. (피보나치 수열이 된다)

 

"n = 3  : "부분에서 연속으로 두 개의 1 타일이 오는 경우를 고려하지 않은 이유는 1개짜리 타일은 단독으로 사용 가능하기 때문에 중복 카운팅 되기 때문이다.

이 부분은 계단 오르기 문제에 대한 풀이 부분에서 자세히 설명을 해 두었다. 위 구문이 이해가 가지 않는다면 링크를 타고 들어가서 풀이 부분만 빠르게 읽어보면 좋을 것 같다. 링크

[백준] 2579번 계단오르기 파이썬 해설

 

정답 코드

---

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

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

위 점화식을 그대로 적용한 케이스이다.

배열의 인덱스는 0부터 시작이지만 가독성 좋은 코드를 작성하기 위해 0번 인덱스는 사용하지 않았다.

출력이 너무 커서 15746으로 나눈 값을 출력하게 되는데, 이 과정에서 주의해야 할 부분이 있다.

결과 값에만 나눠주는 게 아니라 반복문 안에서도 수시로 나머지 연산을 해 주어야 메모리 초과가 발생하지 않는다. (값이 int값을 초과하기 때문에 n = 1000000 일 경우 엄청나게 많은 메모리를 차지하게 된다.)

 

---

사실 나는 정답률이 낮지 않은 문제여서 엄청 우습게 생각했다가 세 번이나 틀렸던 문제이다.

모든 문제를 신중하게 푸는 연습을 해야겠다.