바닥 공사

문제

 

 

입력

• 첫째 줄에 N이 주어진다. (1 <= N <= 1000)

 

 

출력

• 첫째 줄에 2* N 크기의 바닥을 채우는 방법의 수를 796796으로 나눈 나머지를 출력한다.

 

입력 예시

3

출력 예시

5

풀이 방법

d[1] 일 때는  2*1 타일을 놓는 방법이 1개

d [2] 일 때는 2*1 타일을 놓는 방법이 3개이다.

그리고 그림을 그려서 하나하나 보면

d [i-1]까지 타일이 놓였을 때는 2*1 놓는 법이 1개

d [i-2]까지 타일이 놓였을 때는 2개이다.

 

그래서 점화식이 d [i]= d [i-1]+ d [i-2]*2이다

내 코드

n=int(input())

d=[0 for _ in range(n+1)]

d[1]=1
d[2]=3
for i in range (3,n+1):
    d[i]=(d[i-1]+d[i-2]*2)%796796
    
print(d[n])

Solution

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

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])

느낀 점

다이나믹 프로그래밍 문제는 그림으로 그려서 풀면 조금 쉬워지는 것 같다.