[백준/파이썬] 1904번 01타일 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1904번 01타일
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
지원이에게 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이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.
- 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요
코드
a , b = 1, 1
for _ in range(int(input())-1):
a, b = b, (a+b)%15746
print(b)
설명
언뜻 보기에는 코드와 문제에 제시된 내용이 별 상관 없어보입니다.
하지만, 이는 규칙성을 이용한 것입니다.
| n | 만들수 있는 종류 | 개수 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 00, 11 | 2 |
| 3 | 001, 100, 111 | 3 |
| 4 | 0011, 0000, 1001, 1100, 1111 | 5 |
| 5 | 00001, 00100, 10000, 11100, 10011, 00111, 11001, 11111 | 8 |
보시다시피, 만들 수 있는 개수는 (1),1,2,3,5,8,… 으로 피보나치 수열을 따릅니다.
다만 15746으로 나눈 나머지를 출력해야하므로 계산과정에 계속 나머지를 구해줍니다.
덧셈연산이기 때문에 나머지연산에 영향이 없으며, 제때 해주지 않으면 Big Integer로 시간 및 공간 낭비가 발생합니다.
이렇게 만들 수 있는 개수가 피보나치 수열이란 점은 알았습니다. 이것만 알아도 문제를 푸는 데는 충분하지만, 뭔가 찜찜하죠. 정말 이 규칙성이 제대로 적용될지, 어디서 도출되는 규칙성인지 알지 못하는 상태입니다.
진정으로 문제를 풀었다고 볼 수는 없다는 것이죠.
이 규칙성이 어디서 도출되는지 확인해보려면, 이 수가 만들어진 규칙을 보면 됩니다.
n번째에 있는 수는 n-1번째에서 1을 더 쓴 결과죠. 0은 두개가 붙어있는 00의 형태이니 응용할 수 없습니다.
반면, n-2번째는 11 또는 00을 더 쓴 결과로 볼 수 있습니다. 그런데, 이 둘에 중복이 발생합니다. n-2번째에 11을 더 쓴 것은 결과적으로 n-1에 1을 더 쓴것과 중복이됩니다.
즉, n-2번째에 00을, n-1번째에 1을 더 쓴 것만이 필요합니다. 그런데, 이것도 그냥 사용하면 중복이 발생합니다. 예를들어, 11에 00을 더 쓴 것은 0011과 1100이 있겠죠?
그런데 이는 001이나 100에 1을 더 쓴 것들과 중복입니다. 이런 중복을 방지하기 위해, 우리는 이 앞이나 뒤 어느 한쪽에만 00이나 1을 붙일 필요가 있습니다. 이렇게되면, 결국 n번째의 개수는 n-2번째 개수와 n-1번째 개수를 그대로 더하는 것이죠. 이렇게 피보나치 수열이 유도되었습니다.
댓글남기기