N = int(input())
dp = [[0]*10 for _ in range(N)]
temp = [-1,1]
for i in range(N):
for j in range(10):
if i == N-1:
if j == 0:
continue
if i == 0:
dp[0][j] = 1
else:
for k in temp:
nx = j+k
if 0<=nx<10:
dp[i][j] += dp[i-1][j+k]
print(sum(dp[N-1])%1000000000)
# 1309 동물원
# 9901로 나눈 수 출력
N = int(input())
mod = 9901
dp = [0]*(N+1)
if N == 1:
print(3)
else:
dp = [1,3]
for i in range(2,N+1):
current = 2*dp[-1]+dp[-2]
dp[-2] = dp[-1]
dp[-1] = current
print(current%mod)
직접 그려봐서 점화식을 찾았다.
생각해보면 N-1일때, N-1의 위치에 왼쪽에 사자가 있을때, 오른쪽에 사자가 있을때와 둘다 없을때가 있을 것이다.
파란색 음영이 있는 곳이 사자가 있다고 한다고 가정하면, N-1 번 위치에 사자가 있을때에는 2가지의 경우의 수가 있다. 그리고 N-1에 사자가 없을때에는 총 3가지가 있다. 그 중에서 둘다 사자가 없는 경우는 N-2의 크기에서 사자를 놔두는 경우의 수가 같은 것이다.
점화식을 구하면,
F(N) = F(N-1)*2 +F(N-1) 로 나타낼 수 있다.
이렇게 구하고, 전체를 구해서 9901로 나눠도 되지만, 그냥 하면, 숫자가 워낙 커지므로 9901로 나눈 나머지로 계산하는 것이 더 빨리 결과가 나온다.
N = int(input())
prev = 1
result = 3
mod = 9901
for _ in range(N-1):
temp = result
result = (result*2 + prev)%mod
prev = temp
print(result)
# 1149번 RGB 거리
# RGB 거리엔 N개의 집 1~N 순서대로
# 빨 초 파 중 하나
# 비용의 최소값 구하기
# 1번집의 색 != 2번집의 색
# N번집의 색은 N-1 번집의 색과 같지 않아야한다.
N = int(input())
# RGB
arr = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [[INF] *3 for _ in range(N)]
for i in range(3):
dp[0][i] = arr[0][i]
for x in range(1,N):
for y in range(3):
for z in range(3):
if y != z:
dp[x][y] = min(dp[x][y],dp[x-1][z]+arr[x][y])
print(min(dp[N-1]))
처음엔 그냥 dfs를 이용해서 풀어볼려다가, 입력 N이 1000까지라, 3^1000은 시간초과가 날것 같아서 dp로 선회했다.
dp에서 제일 어려운건 동적프로그래밍을 저장할 공간을 설계하는 것 같다. 이 문제를 풀때에 어떻게하면, 이전위치의 저장정보와 최소값 저장할지 고민했었다.
그 해결방법으로 index를 이용했다. dp를 저장하는 y축 index가 동일하지않으면 된다는 점을 착안하여, dp를 설계했다.
