우주의 IT 소행성

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]이 된다.

문제의 규칙성을 계산해보고 풀면 DP문제라는 것을 알아 챌 수 있다.

1 - 1

2 - 1

3 - 2

4 - 3

5 - 5

6 - 8

f(n) = f(n - 1) + f(n - 2) (n > 2 일 경우) 의 점화식을 도출 할 수 있다.

1 / 10 01 / 101 100 / 1000 1010 1001 / 10000 10101 10010 10100 10001 / 100000 101000 101010 101001 100101 100100 100010 100001....