BAEKJOON-1904 : 01타일

BEAKJOON-1904 : 01타일

점화식을 얻을 수 있다면 풀기 쉬운 문제이다.

하지만 문제 조건이 이상하다고 느낀 것이 있는데 바로 출력 부분이다.

만들 수 있는 2진 수열의 개수를 15746으로 나눈 나머지를 출력하라고 했는데

출력할 때만 15746으로 나누는 것이 아니라, 저장할 때마다 15746으로 나눈 나머지를 저장했어야 했다.

15746으로 나누면 뭔가 규칙? 같은게 있나 싶다.

이 부분 때문에 예상했던 시간보다 풀이시간이 길게 걸렸다.

점화식을 빨리 얻을 수 있었던 이유는 코딩테스트에서 비슷한 문제를 봤는데

피보나치 수열과 같은 점화식이란 것을 못 알아내서 실행시간 초과로 못 푼 문제가 있었다.

그 이후 01타일같은 문제를 보면 점화식을 얻어내려고 한다.

코드

n = int(input())
arr = [0, 1, 2]
for i in range(3,n+1):
    arr.append((arr[i-1] + arr[i-2])%15746)
print(arr[n])

코드는 간단한다.

0자리 수 일때 0,

1자리 수 일때 1,

2자리 수 일때 2이고

3자리 수 이상부터는 i자리 수 라고 하면,

i자리 수의 개수 = i-1 자리 수의 개수 + i-2 자리 수의 개수 이런 점화식이 적용된다.

점화식은 3자리 수부터 5자리 수 까지 나타낼 수 있는 수들을 적어보면서 규칙을 알아내서 얻을 수 있었다.

키포인트는 점화식을 적용하는 것과, 수를 저장할 때마다 15746을 나눈 나머지를 저장해야한다는 것.

출력할때만 15746을 나누면 안 된다.