백준 2193: 이친수 (Python)

접근

https://www.acmicpc.net/problem/2193

2193번: 이친수

이친수란 0과 1로만 이루어진 숫자 중 문제에서 주어진 조건들을 만족하는 수이다. N자리 이친수의 개수를 구하기 위해서는 1~N 까지 i자리 이친수의 개수를 구하는 부분 문제들을 풀어야 한다.

이친수를 0으로 끝나는 수와 1로 끝나는 수 두가지로 구분하여 개수를 갱신한다.
0으로 끝나는 i자리 이친수의 경우, i - 1자리 이친수에 아무 조건 없이 0을 추가로 붙여 i자리 이친수를 만들 수 있다.
1로 끝나는 i자리 이친수의 경우, i - 1자리 이친수 중 0으로 끝나는 이친수에만 추가로 1을 붙여 i자리 이친수를 만들 수 있다.
(i - 1자리 이친수 중 1로 끝나는 이친수에 1을 추가로 붙이면 연속해서 1이 나오게 되어 2번 조건에 위배된다.)

위의 조건에 유의하여 갱신하고, 마지막에 0으로 끝나는 N자리 이친수, 1로 끝나는 N자리 이친수를 합하면 답을 구할 수 있다.

코드

N = int(input())
DP = [[0 for _ in range(2)] for __ in range(N + 1)]
DP[1][0] = 0
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])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!