[백준/BOJ] python 1904번 01타일

언어: python

번호: 1904

제목: 01타일

등급: 실버 3

​

풀이:

N=1 > 1

N=2 > 00, 11

N=3 > 100, 001, 111

N=4 > 0000, 0011, 1001, 1100, 1111

N=5 > 10000, 00100, 11100, 00001, 00111, 10011, 11001, 11111

N=i일때 N=i-1일 때와 N=i-2일때를 보면 규칙을 찾을 수 있다. N=i일때 N=i+1인 2진 수열을 만드려면, 앞에서 만든 2진 수열에 1을 붙이거나, 1을 떼고 00을 붙여야 한다. 이때 N-1인 수열의 뒤에 1을 붙이고, N-2인 수열 뒤에 00을 붙이면 중복 없이 새로운 2진 수열을 만들 수 있다. 길이가 N인 모든 2진 수열의 개수는 N번째 피보나치 수와 같다.

​

​

코드:

# 1904 X 
n = int(input())
dp = [0] * 1000001
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])
​

 

 

메모:

DP, dynamic Programming, 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서, 그 결과를 다시 큰 문제를 해결할 때 사용하는 것을 말한다고 한다. 이것만 보면 재귀함수와 유사한다. 차이점은 재귀는 작은 문제의 결과를 기억하지 않는다. 매번 새로 구하는 것이다. 하지만 DP는 그 결과를 저장해 보다 효율적으로 계산할 수 있다.

① Overlapping Subproblems

큰 문제가 같은 여러 개의 작은 문제로 나뉠때 사용한다.

② Optimal Substructure

큰 문제의 크기와 상관 없이 작은 문제의 답이 같다.

이 두가지 조건을 만족해야 DP를 사용할 수 있다.