문제
접근
DP 문제이다.
문제 자체는 몇 개만 나열해보면 규칙이 나온다.
피보나치수열이다.
어떻게 피보나치 수열을 이루는 것일까?
DP[i]는 i자리를 만드는 경우의 수이다.
그럼 DP[i]는 DP[i-2]의 경우들에 앞 뒤로 00을 붙이는 경우가 있을 수 있고,
DP[i-1]에 앞 뒤로 1을 붙이는 경우가 있다.
이를 식으로 표현하면, DP[i] = DP[i-1] * 2 + DP[i-2] * 2가 된다.
근데 이렇게하면 만들어진 수들 중에 중복이 생기게 된다.
정확히 2배..
그래서 나누기 2를 해주면 결국,
DP[i] = DP[i-2] + DP[i-1]이 된다.
더 정확히 말하자면, 앞뒤에 붙이지 않으면 된다.
항상 추가하는 수는 뒤에만 붙이게 되면 중복이 생기지 않고, 위의 식이 나온다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
n = int(input())
dp = [1] * (n+1)
for i in range(2, n+1):
dp[i] = (dp[i-2] + dp[i-1]) % 15746
print(dp[n])