백준 1904 - 01 타일

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

1904번: 01타일

 

결론을 얘기하자면, 해당 문제는 피보나치 수열을 이루고 있기 때문에 그냥 피보나치 수열의 n번째 항을 구해서 출력하면 된다. 하지만, 나는 해당 문제가 피보나치 수열을 이루고 있는지 몰랐기 때문에 풀지 못했다.

이번 포스팅에서는 해당 문제가 왜 피보나치 수열을 이루고 있는지에 대한 원리를 설명해보도록 하겠다.

 

문제를 요약하자면

0은 따로 사용하지 못해서 00 또는 0000 이렇게 두 개의 0을 붙여서 사용해야 되고, 1은 자유롭게 사용이 가능하다.

결국 길이가 n개의 타일을 만들기 위해서는 

 

n = 1 => 1 ==> 1개 

n = 2 => 00 / 11 ==> 2개

n = 3 => 001 / 100/ 111 ==> 3개

n = 4 => 0000 / 0011 / 1001/ 1100/ 1111 ==> 5개

n = 5 => 00001 / 00100 / 10000 / 00111 / 10011/ 11001 / 11100/ 11111 ==> 8개

이렇듯 피보나치 수열의 규칙을 가지고 있다.

 

그렇다면 왜 피보나치 수열이 나오는 것일까?

타일을 나열할 때 선택할 수 있는 경우의 수는 2가지이다. ===> 맨 끝에 0이 올 경우/ 맨 끝에 1이 올 경우

1. 맨 끝에 0이 올 경우 ==> n-2의 길이를 가진 타일의 경우의 수를 갖게 됨

2. 맨 끝에 0이 올 경우 ==> n-1의 길이를 가진 타일의 경우의 수를 갖게 됨

따라서 해당 타일의 경우의 수는 두 경우의 수를 합하여

f(n) = f(n-1) + f(n-2)가 된다.

오늘도 또 문제만 읽고 기계처럼 풀지 말아야겠다는 생각을 했다...쩝

 

정답코드는 다음과 같다.

n = int(input())
f = [0] * (n+1)

if n<=2:
    f[n] = n


if n>2:
    for i in range(3):
        f[i] = i

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

print(f[n])

피보나치 함수를 만들어 재귀적으로 풀이할 수 있기도 하지만, 그러면 굉장히 많은 계산이 일어나기 때문에 n+1 크기의 배열을 만들고 반복문을 돌려서 피보나치 수열을 구하여 값을 넣어놓았다. 그러면 그냥 빼서 쓰기만 하면 되기 때문에 재귀함수로 구현했을 때보다 훨씬 효율적으로 풀이할 수 있다.

 

주의할 점은

n = int(input())
f = [0] * (n+1)
f[0] = 0
f[1] = 1
f[2] = 2
f[3] = 3
for i in range(3, n+1):
    f[i] = (f[i - 2] + f[i - 1]) % 15746

print(f[n])

이건 런타임 에러가 난 코드인데

이 코드를 쓸 경우엔, n이 0이나 1일 경우 f[2]를 선언해버려서 인덱스 초과가 난다.

그래서 n이 2이하일 때는 그 배열의 크기만큼 초기화해주는 코드를 추가로 작성해야 한다.