[백준] 알고리즘 3-5일차 다이나믹 프로그래밍

1. 15988번 : 1,2,3 더하기 3

15988번: 1, 2, 3 더하기 3

1,2,3 더하기와 같은 문제로 풀면된다.

DP[N] = DP[N-1] + DP[N-2] + DP[N-3]

마지막 자리를 1로 할 것인지 2로 할 것인지 3으로 할 것인지를 결정해주면 된다.

매번 테스트케이스때마다 DP안에 있는 값을 계산해주면 너무 비효율적이다.

백만까지 모든 경우를 다구한 이후에 N값을 입력받아 그냥 출력해주면 된다.

문제에서 10억9로 나눈 나머지를 출력하라 했으니 분명 INT의 범위보다 높을 것이므로 LONG LONG으로 설정해준다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[1000001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    dp[1] = 1, dp[2] = 2, dp[3] = 4;
    for (int i = 4; i <= 1000000; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
    }
    while (T--) {
        int n;
        cin >> n;
        cout << dp[n] << "\n";
    }
}

2. 1149번 : RGB거리

1149번: RGB거리

N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

i-1번 , i+1번 집의 색과 같지 않아야 한다. 이말은 i번째와 i-1번째의 색이 같지만 않다면 인접한 두 집사이의 색은 다르게 색칠할 수 있다.

점화식을 세워보면 n번째 집에서 마지막에 무엇을 색칠할 것인가에 대한 변수 j를 둡니다.

 dp[i][0] = min(dp[i - 1][1], dp[i - 1][2])+arr[i][0];
 dp[i][1] = min(dp[i - 1][0], dp[i - 1][2])+arr[i][1];
 dp[i][2] = min(dp[i - 1][0], dp[i - 1][1])+arr[i][2];

i번째에 0번째 색을 선택하였으면 이전인 i-1에는 1번째 색, 2번째 색 둘중 누가와도 상관이 없고, 자기자신을 선택한 비용을 더해주면 됩니다.

마지막에 출력은 어디에 최소의 비용이 들어있는지 모르니 3가지 색중 최소를 출력해주면 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][3]; //n번째집까지 빨강 초록 파랑을 연속해서 사용하지 않고 모든 집을 칠하는 비용의 최솟값을 저장
int arr[1001][3];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> arr[i][j];
        }
    }
    dp[0][0] = arr[0][0], dp[0][1] = arr[0][1], dp[0][2] = arr[0][2];
    for (int i = 1; i < n; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2])+arr[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2])+arr[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1])+arr[i][2];
    }
    cout << min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
}

3. 1309번 : 동물원

1309번: 동물원

DP[i][j] 세로로 N칸 즉 i번째 칸에 j의 경우의 수일때(사자를 놓지않는다(0), 사자를 왼쪽에 놓는다(1), 사자를 놓지 않는다(2)) 사자를 배치하는 경우의 수라고 정의할 수 있다.

사자를 i번째에 놓지않는다면, 이전의 i-1번째에는 모든 경우의 수(사자를 놓지않는다, 사자를 왼쪽에 놓는다, 사자를 오른쪽에 놓는다.)가 가능하다.

사자를 i번째 왼쪽에 놓는다면, i-1번째에는 왼쪽빼고는 다 놓을 수 있다.

사자를 i번째 오른쪽에 놓는다면, 마찬가지로 오른쪽 빼고 다 놓을 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001][3];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2])%9901;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2])%9901;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1])%9901;
    }
    cout << (dp[n][0] + dp[n][1] + dp[n][2])%9901;
}

4. 11057번 : 오르막 수

11057번: 오르막 수

쉬운계단수 문제와 비슷한 문제의 유형입니다.

dp[i][j]를 i 자리수의 길이에 j번째 수가 올때의 오르막 수

j이전의 숫자까지의 길이는 i-1로 j이전 숫자는 오르막 수가되기위해 k<=j라는 식이 성립되어야 한다.

그렇다면, k의 범위는 0<=k<=j 라는 범위가 형성됩니다.

k라는 변수를 둔 이유는 j라는 마지막 자릿수를 결정하였을 때 j이전의 숫자는 어떤 숫자가 올지 모르기 때문입니다.

초기화는 길이가 1인 0~9까지 숫자들이 한개씩 있을 경우니 이경우엔 전부다 1로초기화를 시작해두고 for문을 2부터 돌려 해결할 수 있습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][10]; // i번째 자리수에 j가 왔을때의 오르막수의 개수
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < 10; i++) dp[1][i] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= 10007;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 10; i++) {
        ans += dp[n][i];
        ans %= 10007;
    }
    cout << ans;
}