[BOJ 파이썬] - 01타일 (1904번)
접근
1일때 1개 (1)
2일때 2개 (11, 00)
3일때 3개 (100, 111, 001)
4일때 5개 (1100, 0000, 1001, 1111, 0011)
n 번 째 순열을 잘 보면 n-1, n-2번 순열과 뭔지 모르게 닮았습니다.
또한 반대로 생각해보면 3자리 일때의 순열을 4자리로 만드려면 더할 수 있는 카드는 00은 불가능하니 1밖에 없습니다.
그리고 2자리 일 때의 순열을 2자리로 만드려면 01, 10, 11, 00 을 붙일 수 있는데 01, 10, 11은 이미 3자리 일때에 사용하고 있죠. 그래서 00을 붙여야만 4자리로 만들 수 있습니다.
즉, n자리의 순열을 만들기 위해서는 n-1의 순열에 1을 더한 순열들의 합과
n-2의 순열에 00을 더한 순열들의 합을 더하면 되겠습니다.
이것을 식으로 정리하면 n = n-1 + n-2가 됩니다.
풀이
import sys
n = int(sys.stdin.readline())
dis = [0] * (n + 1)
dis[1] = 1
if n > 1: dis[2] = 2
for i in range(3, n+1):
dis[i] = (dis[i-1] + dis[i-2]) % 15746
print(dis[n])
여담
저는 바텀-업 방식으로 풀었지만 재귀를 이용한 탑-다운 방식으로도 풀 수 있습니다.
Author And Source
이 문제에 관하여([BOJ 파이썬] - 01타일 (1904번)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rmsry123/BOJ-파이썬-01타일-1904번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)