[백준 2024/10/11] 2193번 이친수

1. 문제

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

 

2. 접근 방법

 

1과 0이 있을 때, 1에서는 항상 0 하나의 경우의 수만 발생하고,  0에서는 항상 1과 0. 2개의 경우의 수가 발생한다.

따라서, 리스트로 0의 개수와 1의 개수를 나타내도록 하였으며, [a, b] 라고 가정했을 때, [a+b, a] 로 다음 단계가 진행된다.

 

        dp[i][0] = dp[i-1][0] + dp[i-1][1]
        dp[i][1] = dp[i-1][0]

 

3. 코드

def get_nums(n, dp):
    dp[1] = [0, 1]
    dp[2] = [1, 0]

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

    return sum(dp[n])


if __name__ == "__main__":
    n = int(input())
    dp = [[0,0] for _ in range(92)]
    print(get_nums(n, dp))