import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 8)
sys.stdin.readline
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])
N의 범위가 1부터 1000까지이므로 d배열을 1001개만큼 설정해주고,
d[1] = 1, d[2] = 3은 직접 그림을 그려보면서 케이스 분류를 통해 알 수 있었다.
만약 1x2 도형을 사용한다면 , 남는 도형은 가로 N-1, 세로 2
만약 2x1, 2x2 도형을 사용한다면 남는 도형은 가로 N-2, 세로 2
따라서 d[i] = d[i-1] + (2*d[i-2])라는 식을 도출해낼 수 있었다.
다이나믹 프로그래밍은 급하게 식을 세우기보단 고민해보면서 관계식을 도출하는 것이 1순위
'알고리즘 문제 풀이' 카테고리의 다른 글
이코테 개선된 다익스트라 알고리즘 코드 (0) | 2023.07.04 |
---|---|
[백준] 이분탐색 1920번 파이썬 풀이 (0) | 2023.06.29 |
[이코테] 다이나믹 프로그래밍 실전문제 3번 (0) | 2023.06.29 |
[이코테] 이진 탐색 실습문제 3번 (0) | 2023.06.28 |
[이코테] 이진탐색 실전문제 2번 풀이 (0) | 2023.06.27 |