[백준/파이썬]1904 01타일

 

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

1904번: 01타일

 

문제

백준 1904번

'1'

'00'

이 두 개의 문자열을 이용해 n에 해당하는 문자열을 만들면 되는 문제 같았다.

 

 

 

일단 문제를 읽고 대충 생각나는 대로 재귀로 풀어봤다.

 

def make_bin(s) :
    if len(s) == n :
       return 1
    elif len(s) > n :
        return 0
    else :
        return make_bin(s+'00') + make_bin(s+'1')


n = int(input())
s = ""

print(make_bin(s)%15746)

일단 입력이 1,000,000까지 들어오니 당연히 재귀로는 못 풀거라 생각을 했다.

 

그렇지만 재귀로 풀고 나서 1~10까지 출력을 해보니

이런 결과가 나왔다. 그리고 어디서 보던 수열이 보이기 시작했다.

 

그래서 나는 이 문제가 피보나치와 똑같은 문제구나!라고 생각하고 코드를 짰다.

 

정답

n = int(input())
arr = [0 for i in range(1000001)]
arr[0], arr[1] = 1, 1

for i in range(2, 1000001, 1) :
    arr[i] = (arr[i-1] + arr[i-2])%15746

print(arr[n])

운 좋게 풀었던 문제 같다.

 

구글링 해 보니

 

문제의 특정을 보고 점화식을 도출해 내서 푸는 문제 같았다.

 

아마 문제에서 설명할 때

N = 1, 2, 4 순으로 설명해 주는데 3까지 설명해 주면 피보나치로 다들 눈치챌까 봐 설명하지 않은 것 같다 ㅋㅋ

 

---

이런 문제를 보고 식을 찾는 게 단순히 운으로만 풀리면 안 될 텐데 라는 생각을 가지게 한 문제.