[백준] 1904 파이썬(python) : 01타일 - dp기초

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

1904번: 01타일

 

 

dp의 대표적인 유형인 타일 문제이다.

n이 입력되었을때 타일 00과 1을 이용하여 길이 n의 타일을 만들 수 있는 경우의 수를 구하는 문제다.

dp를 사용하면 시간 복잡도 O(N)으로 해결할 수 있다.

타일은 1 과 00만 사용할 수 있으므로

 

n = 1일때는 1 -> 1가지

n = 2일때는 00 -> 1가지

n = 3일때는 001, 100, 111 -> 3가지

n = 4일때는 0011, 0000, 1001, 1111, 1100 -> 5가지

 

이런식으로 만들 수 있다.

 

점화식을 세워보면 다음과 같다.

 

i번째 인덱스일때 만들 수 있는 타일의 경우

 

현재 위치에서 마지막 인덱스는 i이니까 i번째 인덱스에 올 수 있는 타일은 00과 1 두가지 뿐인데 위의 사진처럼 된다.

 

i-1번 인덱스까지의 합과 i번째에서 타일 1이 오는 경우와 i-2번 인덱스까지의 합과 i-1과 i번째 인덱스에서 00이 오는 경우이다.

 

이 두가지 경우를 합치면 n의 길이를 가진 타일을 만들 수 있는 경우의 수를 구할 수 있다.

 

n = int(input())
dp = [0]*1000001 #1
dp[1] = 1 #2
dp[2] = 2 #3
for i in range(3, n+1): #4
    dp[i] = (dp[i-2] + dp[i-1]) % 15746 #5
print(dp[n])

 

#1 : 입력값이 백만이니까 백만일로 dp리스트 생성

#2, 3 : 각각 길이가 1일때의 경우는 1개 길이가 2일때의 경우는 1개이다.

#4 : 확정할 수 있는 길이는 2까지 이므로 3부터 n까지 반복 수행

#5 : 각 경우의 수에 15746을 나머지 연산해준 값을 저장하고 dp[n]을 출력

 

---

2579번 계단 오르기

뒤에서 부터 올라가는 바텀업 문제 : 14501 퇴사