[백준] 2193 - 이친수

아이데이션

연속해서 숫자를 배열하는 문제를 풀어서 그런가 보자마자 2차원 dp로 풀어야겠다고 생각한 문제였다.
사실 숫자가 0과 1밖에 없어서 1차원 dp 만으로도 풀리는 문제긴 하다!!

왜그런지 좀 더 자세히 살펴보자

문제에서 주어진 조건은 총 두개이다.

1. 0으로 시작하지 말 것

2. 1이 두번 연속으로 배열되지 말 것

 

이 말은 이렇게도 바꿀 수 있다.

n자리 수의 i번째 자리의 숫자를 넣을 때,

1. 1번째 자리는 1만 넣을 것

2. i - 2까지의 경우의 수에서 01을 넣거나,
i - 1까지의 경우의 수에서 0을 넣을 것

이 관계를 수식으로 나타내면 다음과 같다

cache[i] = cache[i - 2] + cache[i - 1]

 

풀이

 

n = int(input())
cache = [[0] * (n + 1) for _ in range(2)]
cache[1][1] = 1

for column in range(2, n + 1, 1):
    for row in range(2):
        if(row == 0):
            cache[row][column] = cache[row][column - 1] + cache[row + 1][column - 1]
        else:
            cache[row][column] = cache[row - 1][column - 1]
print(cache[0][n] + cache[1][n])