2193 이친수

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

N = int(input())
dp_table = [[0,0] for _ in range(90)]
dp_table[0] = [1,1]

for i in range(1,N):
    dp_table[i][0] = sum(dp_table[i-1])
    dp_table[i][1] = dp_table[i-1][0]

print(dp_table[N-1][1])

3. 문제 풀이

다이나믹 프로그래밍 문제들은 N=1부터 계속해서 적어나가면서 가지를 만들어야 규칙을 찾기 쉽다.

그림을 먼저 보자.

0으로 시작하지 않는 문제같은 경우는 대부분 0의 경우를 dp table에 넣어주는게 핵심이다. 이 문제에서도 1로 시작하는 수 아래에는 무조건 0이 나와야하기때문에 i번째 1의 아래의 0은 i-1번째의 0의 가지를 의미한다.(빨간색 라인) 이렇게 그림을 그리고 dp table의 index로 표현을 해보면 쉽게 규칙을 찾아낼 수 있다.