[BOJ/Step15] 1904 : 01타일 (Python)

www.acmicpc.net/problem/1904

1904번: 01타일

---

쭉 가능한 타일을 나열해보면 규칙을 찾을 수 있다

n=1 (1)  : 1

n=2 (2) : 00 11

n=3 (3) : 001 100 111

n=4 (5) : 0000 0011 1001 1100 1111

n=5 (8) : 00001 00100 00111 10000 10011 11001 11100 11111

…

 

f(n) = f(n-1) + f(n-2) 라는 것을 알 수 있다

 

(1) 배열을 사용하는 방법

  1. 배열 array에 미리 0, 1, 2, 0, 0, 0, … 을 넣어둔다

  2. for문을 통해 array[3]부터 채워나간다 array[n] = ( array[n-1] + array[n-2] ) % 15746

  3. n번째까지 채운 후 array[n]을 출력

# 1904-1.py

n = int(input())
array = [0, 1, 2] + [0] * n

for i in range(3, n+1):
    array[i] = (array[i-1] + array[i-2]) % 15746

print(array[n])

 

(2) 변수만 사용하는 방법

  1. 변수 a, b 에 각각 1, 2를 저장한다

  2. a에는 b를, b에는 a + b % 15746을 저장한다

  3. n-1번 반복한 후 a를 출력한다 ( 미리 1, 2 를 저장해 두었기 때문에 n번이 아닌 n-1번 반복 )

# 1904-2.py

n = int(input())
a, b = 1, 2

for _ in range(n-1):
    a, b = b, (a + b) % 15746

print(a)

 

 

위부터 (1) (2) 번 코드

(2)번 코드가 메모리가 적게 드는건 당연한데

속도는 왜 빠른걸까..? 의문