[다이나믹 프로그래밍] 바닥 공사 (실전문제, 이것이 코딩테스트다 with 파이썬)

다이나믹 프로그래밍(Dynamic Programming) (= 동적 계획법)

메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

 

문제

 

해설

앞부터 점차 늘려가며 경우의 수를 구하면 됨

 

* 풀이 아이디어 : 점화식

1. (이전까지의 경우의 수) * (끝에 한 칸 남음) → 이전까지의 경우의 수 그대로
2. (이전까지의 경우의 수) * (끝에 두 칸 남음) → 이전까지의 경우의 수 두배

 

풀이

# 정수 N을 입력받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍 진행(보텀업)
# 계수 1부터 시작(인덱스)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796
    
# 계산된 결과 출력
print(d[n])

 

해석

변수 : N 가로의 길이, d 보텀업에서 DP테이블, i 현재의 수

 

1. 가로의 길이 N 입력받기

2. DP테이블 초기화 : [0] * 1001

-------- 다이나믹 프로그래밍 : 모든 경우의 수 --------

ㄴ 현재의 수 i

ㄴ 3 ~ x 까지의 반복문 수행    # 계수 1부터 시작

3. 첫째 항

ㄴ d[1]의 경우의 수 : 1

ㄴ d[2]의 경우의 수 : 3

4. 일반항 : 경우의 수 업데이트

ㄴ d[i] = d[i - 1] + 2 * d[i - 2]    # 경우의 수(끝에 1 남기는 경우 or 끝에 2 남기는 경우)

--------------------------------------------------------------------

6. 전체 경우의 수로 자동 업데이트되어 d[x] 출력