#86. 이친수 구하기

1. 문제 분석하기

1. 자릿수
   • 처음 숫자는 무조건 1
2. 0으로 끝나는 이친수 vs 1로 끝나는 이친수
   • 2차원 배열 점화식 선언: D[N][2]

2. 손으로 풀어보기

1. 점화식의 형태/의미 도출

   D[i][0]: i 길이에서 끝이 0으로 끝나는 이친수의 개수
   D[i][1]: i 길이에서 끝이 1로 끝나는 이친수의 개수
   

2. 점화식 구하기

   • 조건) 1은 두 번 연속으로 나오지 않는다.

     

3. 점화식을 이용해 DP 테이블을 채운 후 D[N][0] + D[N][1] 값 출력

   

3. Pseudo Code

D # 점화식 테이블
# D[i][0]: 길이 i에서 끝이 0으로 끝나는 이친수의 개수
# D[i][1]: 길이 i에서 끝이 1로 끝나는 이친수의 개수

N # 자릿수
D[1][1] = 1 # 1자리 이친수는 1 한 가지만 있음
D[1][0] = 0 # 이친수는 0으로 시작 x -> 1

for i = 2 to N:
	i번째 0으로 끝나는 개수 = (i-1)번째에서 0으로 끝나는 개수 + 
	                        (i-1)번째에서 1로 끝나는 개수

N번째에서 0으로 끝나는 개수 + N번째에서 1로 끝나는 개수 출력 

4. 코드 구현하기

import sys
input = sys.stdin.readline

## 입력
N = int(input())
D = [[0 for j in range(2)] for i in range(N+1)]
D[1][1] = 1 # 1자리 이친수는 1 한 가지만 있음
D[1][0] = 0

## 처리
for i in range(2, N+1):
    D[i][0] = D[i-1][1] + D[i-1][0]
    D[i][1] = D[i-1][0]

## 출력
print(D[N][0] + D[N][1])

#90 최장 공통 부분 수열 찾기

1. 문제 분석하기

• 각 문자열의 문자를 축으로 하는 2차원 리스트를 생성

  

• 이렇게 구성한 2차원 리스트가 점화식 테이블이 됨

  • 각 위치 인덱스를 마지막 문자로 하는 두 문자열의 최장 공통 수열의 길이를 저장

2. 손으로 풀어보기

0) 초기 테이블 → 0으로 초기화