Coding 공부

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를 설계했다.