[Baekjoon] 1904번 : 01타일 (Python)

[Baekjoon] 1904번 : 01타일 (Python)

 

목차

 

 

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

1904번: 01타일

Python

 

방법 1 - 메모리 29380KB / 시간 308ms / 코드 길이 

우연히도 계산의 결과가 나열 순서는 피보나치이고 피보나치를 DP(재귀 + Memorization)로 풀어낼 수 있다.

1:1, 2:2, 3:3, 4:5, 5:8, 6:13

N = int(input())
a, b = 0,1
t = 0
for _ in range(N):
    t = (a + b) % 15746
    a = b % 15746
    b = t
print(t)

 

방법 2 - 메모리 69396KB / 시간 392ms / 코드 길이 125B

Bottom-Up 방식의 DP 

N = int(input())
d = [0] * 1000001
d[1], d[2] = 1, 2
for i in range(3, N+1):
    d[i] = (d[i-1] + d[i-2]) % 15746
print(d[N])

 

간혹 피보나치를 행렬 곱으로 풀어낸 풀이법이 존재하는데 해당 부분은 생략.

 

[[F_n+1, F_n],[F_n, F_n-1]] = [[1,1],[1,0]]

 

번외 - 메모리 초과

list에 가능한 방법을 모두 저장하여 확장하는 방식을 채택해보려했으나 많은 메모리를 사용하기에 메모리 초과가 되었다.

규칙이 없는지, 점화식은 가능한지를 먼저 확인해야 문제가 편해질 것으로 보인다.

 

만약 메모리 문제만 아니었다면 맞았을 것으로 예상한다.

 

def t(n):
    if n == 1:
        return '1'

    l=['00','1']
    b = True
    while b:
        p = []
        k=0
        for i in l:
            if n-len(i) >= 2:
                p.append(i + '00')
                p.append(i + '1')
            elif n-len(i) == 1:
                p.append(i + '1')
            elif n-len(i) == 0:
                k += 1
                p.append(i)

        if k == len(l):
            b = False
        l=p
    return len(l)

n = int(input())
print(int(t(n)) % 15746)