[BOJ] 2193번 : 이친수

🔒 문제

⌨ 입력

🖨 출력

📚 예제

📌 풀이

문제를 딱 보면 끝이 0인 애들은 뒤에 0이나 1이 올 수 있고, 끝이 1인 애들은 0밖에 못오는 것을 알 수 있다.

그래서 생각한게 0으로 끝나는 수와 1로 끝나는 수들의 개수를 따로 저장하는 것이었다.

그래서 1차원 배열이 아닌 2차원 배열로 dp를 만들어서 끝이 0인 수의 개수는 0열에, 끝이 1인 수의 개수는 1열에 저장하기로 한다.

n	0으로 끝나는 수	1로 끝나는 수
1	-	1
2	10	-
3	100	101
4	1010, 1000	1001
5	10100, 100000, 10010	10101, 100001

위의 표를 개수로 나타내 보겠다

n	0으로 끝나는 수들의 개수	1로 끝나는 수들의 개수
1	0	1
2	1	0
3	1	1
4	2	1
5	3	2
...	...	...
n - 1	dp[n - 1][0]	dp[n - 1][1]
n	dp[n - 1][0] + dp[n - 1][1]	dp[n - 1][0]

따라서 식을 말해보자면

1. n == 1
dp[1][0] = 0
dp[1][1] = 1

2. n > 1
dp[n][0] = dp[n - 1][0] + dp[n - 1][1]
dp[n][1] = dp[n - 1][0]

🔑 python 코드

# 이친수
import sys
input = sys.stdin.readline
n = int(input())

dp = [[0, 0] for _ in range(n + 1)]
dp[1][1] = 1

for i in range(2, n + 1):
    dp[i][0] += dp[i - 1][0] + dp[i - 1][1]
    dp[i][1] += dp[i - 1][0]

print(dp[n][0] + dp[n][1])