[Python] 백준 1904번:01타일 / 문제 풀이, 설명

[Python] 백준 1904번:01타일 / 문제 풀이, 설명

---

º 코드

def Dp(n):
    a = [1,1]
    if n>=2:
        for i in range(2, n+1):
            a.append((a[i-1]+a[i-2])%15746)
    return a[n]

print(Dp(int(input())))

 

º 풀이

1. 전체적인 코드 풀이

• Bottom - Top, 상향식으로 a 리스트를 채워나가 값을 구함

2. 함수 설명

def Dp(n):
    a = [1,1]
    if n>=2:
        for i in range(2, n+1):
            a.append((a[i-1]+a[i-2])%15746)
    return a[n]

• n과 배열 Index를 맞춰주기 위해서 배열을 [1,1]로 정의해서 for을 이용해 n까지 채워나갔다.

---

º 풀이 과정

1. 2진 수열 타일이 있는데 0은 00의 형태로만 쓰인다. N이 주어질 때 가짓수를 15746으로 나눈 나머지를 출력!
2. N이 1일 때 ( 1 ), 2일 때 (11, 00), 3 = (111, 100, 001 ), 4 = (1111, 1100, 0011, 0000, 1001 ) // f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5 
3. 결국 N>=3 일 때 f(N) = f(N-1) + f(N-2)가 된다. N의 범위가 매우 크기 때문에 Down-top 방식인  Tabulation을 이용

---

º 도움이 된 사이트

• https://namu.wiki/w/%EB% 8F%99% EC% A0%81%20% EA% B3%84% ED% 9A% 8D% EB% B2%95

동적 계획법 - 나무위키