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

연속, 인접이라는 처리는 마지막에 무엇이 오는지 기록하는 방식으로 문제를 해결한다.

1. 15990번 : 1,2,3 더하기 5

15990번: 1, 2, 3 더하기 5

DP[i][j] i를 1, 2, 3의 합으로 나타내는 방법의 수와 j가 마지막에 오는 경우의 조건을 추가한 점화식

이전에 풀었던 문제와 다른점은 조건이 하나 추가되었기 때문에 연속된 숫자의 경우를 배제해야한다.

DP[i][1] i를 합으로 나타내는데 마지막에 1이 오는경우는 = DP[i-1][2] + DP[i-1][3] i-1까지의 마지막 숫자가 1만아니면 된다.

즉 마지막에 오는 숫자를 제외하고 계산해주면 점화식이 완성된다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[100001][4]; // n을 1,2,3의 합으로 나타내는 방법의 수 끝자리가 1,2,3으로 끝나는
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    long long mod = 1000000009;
    cin >> T;
    dp[1][1] = 1,dp[2][2]=1,dp[3][3]=1,dp[3][1]=1,dp[3][2]=1;

    while (T--) {
        int n;
        cin >> n;
        for (int i = 4; i <= n; i++) {
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3])%mod;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3])%mod;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2])%mod;
        }
        cout << (dp[n][1] + dp[n][2] + dp[n][3])%mod<<"\n";
    }
}

2. 10844번 : 쉬운 계단 수

10844번: 쉬운 계단 수

연속된 수를 처리해주기 위해서 조건에 부합하는 2차원 배열을 생성해야 한다는 것을 생각해본다.

DP[N] = 길이가 N인 계단 수가 총 몇 개있는지로 설정하면 인접한 자리수의 차이가 1이 되는지 알 수 있는 방법이 없다.

DP[i][j] = 길이가 i의 계단에 마지막 계단이 j인 경우로 설정해볼 수 있다.

그렇다면 DP[i][j] = 한 개의 계단을 고른상태이니 전체 i개중에서 길이가 i-1인 계단의 마지막부분이 j와 1차이가 나면된다.

즉 DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1] 로 설정할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[101][11]; // 길이가 n인 계단수에 마지막에 오는 수를 저장
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    long long mod = 1000000000;
    cin >> n;
    for (int i = 1; i < 10; i++) {
        dp[1][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j + 1];
                
            }
            else if (j == 9) {
                dp[i][j] = dp[i - 1][j - 1];
                
            }
            else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
            dp[i][j] %= mod;
        }
    }
    long long ans=0;
    for (int i = 0; i <10; i++) {
        ans += dp[n][i];
        ans %= mod;
    }
    cout << ans;
}

3. 2193번 : 이친수

2193번: 이친수

DP[N] = N자리 이친수의 개수를 구하는 문제

조건에서는 1이 두 번 연속으로 나타나면 안되고, 길이가 1일때 0으로 시작하지 않는다는 것을 알 수 있다.

그렇다면 이전의 문제와 같게 2차원 배열을 만들어서 해결할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[91][2]; // 길이가 n인 계단수에 마지막에 오는 수를 저장
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][1]+dp[i-1][0];
        dp[i][1] = dp[i - 1][0];
    }
    cout << dp[n][0] + dp[n][1];
}