우주의 IT 소행성

https://www.acmicpc.net/problem/1309

n = int(input())
d = [[0] * 3 for _ in range(n + 1)]
d[0][0] = 1

for i in range(1, n + 1):
    d[i][0] = d[i - 1][0] + d[i - 1][1] + d[i - 1][2]
    d[i][1] = d[i - 1][0] + d[i - 1][2]
    d[i][2] = d[i - 1][0] + d[i - 1][1]
    for j in range(3):
        d[i][j] %= 9901
print(sum(d[n]) % 9901)

D[N] = 세로로 n칸인 동물원에서 가능한 배치의 수
d[n][m] = 세로로 n칸인 동물원, 마지막 칸은 m번 방법을 사용한 배치의 수
m : 0 배치하지 않음
m : 1 왼쪽 배치
m : 2 오른쪽 배치

https://www.acmicpc.net/problem/1149

n = int(input())
a = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[0, 0, 0] for _ in range(n + 1)]

for i in range(1, n + 1):
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2]
print(min(d[n][0], d[n][1], d[n][2]))

RGB 거리, R = 0, G = 1, B = 2 라고 하고
A[i][j] = i번 집이 j번색일 경우 로 가정하자.
1. i의 이웃은 i - 1, i + 1
2. 첫 집과 마지막 집은 이웃이 아니다.
3. 모든 이웃은 다른 색의 집이다.
- 연속하는 집을 같은 색으로 칠할 수 없다.

d[i][0] = min(d[i - 1][1], d[i-1][2]) + a[i][0]
d[i][1] = min(d[i - 1][0], d[i-1][2]) + a[i][1]
d[i][2] = min(d[i - 1][0], d[i-1][1]) + a[i][2]
정답 : min(d[n][0], d[n][1], d[n][2])

https://www.acmicpc.net/problem/2225

MOD = 1000000000
n, k = map(int, input().split())
d = [[0] * (n + 1) for _ in range(k + 1)]
d[0][0] = 1
for i in range(1, k + 1):
    for j in range(0, n + 1):
        for l in range(0, j + 1):
            d[i][j] += d[i - 1][j - l]
        d[i][j] %= MOD
print(d[k][n])

x + x + x + ... + L = N
일 때, L 이전까지의 수열들
합 = N - L개
개수 = K - 1개
이므로, D[K][N] = D[K - 1][N - L]이 된다.

다이나믹 프로그래밍, 메모이제이션을 사용하여 풀어야 하는 문제이다.

2xN 직사각형을 1x2, 2x1, 2x2 타일로 채우는 경우의 수를 구를 2X(최대 1000)까지 구한다.

즉 반복되는 작업을 한다 -> 수열이 형성된다 라는 점을 기억해야한다.

1*2 -> A

2*1 -> B

2*2 -> C

라고 생각해보자

1) N이 1일 때

- B 한가지만 들어갈 수 있다.

- F(1) = 1

2) N이 2일 때

- AA, BB, C

- F(2) = 3

3) N이 3일 때

- AAB, BAA, CB, BC, BBB

- F(3) = 5

4) N이 4일 때

- AAAA, BBBB, AABB, BBAA, BAAB, AAA, CAA, BBC, CBB, BCB, CC 

- F(4) = 11

이 떄, N이 4 이상일 경우, F(N) = F(N - 1) + (F(N - 2) * 2)

의 일반항을 도출할 수 있고 이를 메모이제이션하여 출력해주면 된다.

문제의 반복성과 규칙성을 찾아내 일반항을 도출하는 것

-> 다이나믹 프로그래밍으로 해결할 수 있다.