[백준] 2193번: 이친수

💻 문제 - S3

n이 1일 때 1 -> 1
n이 2일 때 10 -> 1
n이 3일 때 100, 101 -> 2
n이 4일 때 1000, 1001, 1010 -> 3
n이 5일 때 10000, 10000, 10010, 10100, 10101 -> 5
...

개수로 보았을 때 dp[n] = dp[n-1] + dp[n-2]라는 점화식을 얻을 수 있지만,
이친수의 수를 보았을 때 그리고 1이 연속되지 못한다는 것을 고려했을 때, 맨뒤에 0/ 1/ 100, 101/ 1000, 1001, 1010이 반복되고 있어서 다음과 같은 방법으로 풀이하였다.

👉 제출 코드

n = int(input())
dp = [1, 1, 1, 2] + [0] * (n-3)
for i in range(4, n+1):
    dp[i] = sum(dp[:i-1])
print(dp[n])

dp[0]을 1로 초기화하고, 0부터 i-2까지의 합으로 갱신한다.

🙏 다른 사람의 풀이 보기

n = int(input())

s = [0, 1, 1]

for i in range(3, n+1):
    s.append(s[i-1] + s[i-2])

print(s[n])

개수로 보았을 때 위와 같은 풀이 또한 성립한다.