BAEKJOON 1904
문제
지원이에게 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이 주어진다.(N ≤ 1,000,000)
나의 처음 코드
제일 처음 문제를 풀 때, dp문제가 아니라 나름 어떠한 공식을 가지고 있는 문제인 줄 알았다. 그래서 그 방식으로 문제를 풀었다. 그 코드는 아래와 같다. (설명이 짧은 이유 틀려서~)
N = int(input())
count = 0
for i in range(N//2 + 1):
if 2 * i == 0:
count += 1
elif 2 * i == N:
count += 1
elif 2 * i < N:
count = count + (N-(2*i)) + i
print(count%15746)
결과는 틀렸습니다. 내가 생각했던 방식대로 갯수가 흘러가지 않았다. 다른 방식으로 생각해보자. 아래의 몇개의 예시를 봐보자.
1 -> 1
00 11 -> 0 3
001 100 111 -> 1 4 7
1111 0011 1001 1100 0000 -> 0, 3, 9, 12, 15
즉, n이 주어졌을 때, 생길 수 있는 가지수는 홀수일 경우 1부터 시작해서 3씩 증가해, (2의 n승 -1) 까지, 짝수일 경우에는 0부터 시작해서 3씩 증가해, (2의 n승 -1) 까지이다. 점화식을 세워보면 알겠지만, 이 문제 또한 피보나치 수열이 적용되는 문제이다. 따라서 여느 dp 피보나치 수열 문제처럼 문제를 풀어주면 된다.
—–
정답
N = int(input())
fibo = [1, 2, 3, 5] #기존에 예시로 든 갯수들
if N-1 < 4: #이미 있기 때문에
pass
else: #없으면 피보나치 수열처럼 차례차례 메모라이징 하면서 구해준다
for i in range(4, N):
fibo.append((fibo[i-1] + fibo[i-2]) % 15746)
print(fibo[N-1])
너무 성급하게 문제를 바라보는 습관을 버려야 한다. 문제를 다방면으로 살펴보는 능력을 키워보자~!