1904_01타일

문제는 더보기!

 

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력 1 복사

4

예제 출력 1 복사

5

처음에 고민을 하다가 문제를 꼼꼼히 보다보니 N의 입력값이 엄청 큰걸 발견했다.

 

보통 타일이 2개면 2의 2제곱, 5개면 2의 5제곱처럼 기하급수적으로 늘어나게된다.

 

이걸 보고 순열의 조합이나 다른 방식으로는 풀기 어려운 문제라는걸 깨닫고 규칙이 있나 계속 생각해봤다. 맨 처음에는 00과 1로 이루어지는 경우의수등을 찾으려 했는데 그것또한 4개면 [1,1,1,1] [1,00,1] [00,00] 위처럼 순열을 생각해줘야하는 조합만 3개가 나온다는 걸 생각했다.

 

그래서 규칙성이 있나 찾아보려고 7까지 무지성으로 값을 계산해보았더니 규칙성이 보였다.

바로 피보나치수열처럼 전값과 그전값의 합이 다음 답의 값이었다.

 

# 1 : 1 > 1 + 0
# 2 : 2 > 1 + 1
# 3 : 3 > 1 + 2 + 0
# 4 : 5 > 1 + 3 + 1
# 5 : 8 > 1 + 4 + 3 + 0
# 6 : 13 > 1 + 5 + 6 + 1
# 7 : 21 > 1 + 6 + 10 + 4

즉 1+ 2 > 3

2 + 3 >5 이런 꼴로 전개되는것같은 양상으로 보였다. 그 후엔 큐 구조를 이용해서 피보나치 수열의 값을 구하듯이 코드를 짜 보았다.

 

N = int(input())
lst =[1,2]

for i in range(2,N):
    lst.append((lst[0]+lst[1])%15746)
    lst.pop(0)
print(lst[0] if N==1 else lst[1] )


# 1 : 1 > 1 + 0
# 2 : 2 > 1 + 1
# 3 : 3 > 1 + 2 + 0
# 4 : 5 > 1 + 3 + 1
# 5 : 8 > 1 + 4 + 3 + 0
# 6 : 13 > 1 + 5 + 6 + 1
# 7 : 21 > 1 + 6 + 10 + 4

첫번째 값인 N이 1인 경우에만 예외처리를 해준다면 무사히 통과할 수 있다.

 

이런문제는 수학적으로 푸는것도 좋은 방법같다 ^^!