[이코테] CH08 다이나믹 프로그래밍 실전문제 4번 바닥 공사

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
N = int(input())
d = [0] * 1001
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])

하아 어렵다.....

보텀업 방식으로 푸는 만큼

d[i]와 이전 항들의 관계를 잘 생각해야 하니까

d[i-1]과 d[i-2], 어떤 관계가 성립할까?

d[i-1]인 경우에는 2*1짜리 타일 한개만 붙여주면 된다.

d[i-2]인 경우에는? 1*2 타일 2개를 붙이거나 / 2*2 타일을 하나 붙이면 된다.

그래서 d[i-2] * 2가 유도된 것이다.

 

도서관와서 코딩하는 중인데

담배 폈으면

제발 냄새는 뺴고 오면 좋겠다.

저런 민폐를 주는 어른이 되진 말아야지 항상 다짐하고는 합니다..