220713 PS 일기 : 각종 DP 문제들 풀이 (O(N^2) 실버~골드 난이도)

백준 BOJ 9764번 : 서로 다른 자연수의 합

문제 난이도 : Silver I

알고리즘 분류 : DP

 

자연수 N을 서로 다른 자연수들의 합으로 나타내는 방법의 수를 구하는 문제이다.

아주 아주 기초적인 DP 문제임에도 점화식을 못 떠올려서 꽤 오래 막혔고, 풀이를 참고했다.

점화식은 다양한 방법으로 세울 수 있겠으나, 참고한 풀이는 "dp(a, b) : b 이하의 수들의 합으로 a를 만드는 경우의 수"와 같이 dp를 정의하는 것이다.

그렇게 한다면 b를 증가시켜 가면서 dp(a, b) = dp(a-b, b+1) + dp(a, b+1) (즉, b를 a의 합에 넣어주는 경우와 그렇지 않은 경우의 합) 탑다운 방식으로 답을 구해줄 수 있다.

 

처리해야 할 예외는 다음과 같다.

1. dp 값이 이미 구해진 경우 (memset을 -1로 해주면 쉽게 구분 가능하며 dp != -1이면 dp 값을 리턴해주면 된다.)

2. N < x인 경우 : 정의는 가능(dp(N, x)와 같은 값)하지만 점화식을 합으로 구하고 있으므로 0을 리턴해주어야 한다.

3. N = 0인 경우 : 앞에서 걸러졌고 N = 0이라면 x = 0이므로, 1으로 정의해주어야 한다.

4. N = x인 경우 : N = N으로 한 가지 표현 방식이 존재하므로 1을 리턴해주면 된다.

 

 

#include <bits/stdc++.h>
using namespace std;

int dp[2001][2001];
int mod = 100999;

int f(int N, int x) {
    if(dp[N][x] != -1) return dp[N][x];
    if(N < x) return dp[N][x] = 0;
    if(N == 0 || N == x) return dp[N][x] = 1;

    return dp[N][x] = (f(N-x, x+1) + f(N, x+1)) % mod;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        memset(dp, -1, sizeof(dp));

        cout << f(N, 1) << "\n";
    }
}

 

 

백준 BOJ 12849번 : 본대 산책

문제 난이도 : Silver I

알고리즘 분류 : DP, 그래프 이론

 

 

위와 같은 그래프가 주어질 때, D번 이동하여 정보과학관에 도착할 수 있는 경우의 수를 구하는 문제이다.

 

처음에는 그래프 연결 관계를 행렬로 옮긴 뒤 행렬을 곱해야 하나 생각했는데 D가 10만 이하라서 '분할정복을 이용한 거듭제곱'을 사용해줄 필요가 없고, 연결이 그리 많지 않으므로 1차원 배열에 계속해서 더해주는 방식을 사용하면 된다.

노드 번호는 위에 나온 그림대로 매겼다. (문제에 없는 번호인데 내가 임의로 그린 것이다.)

 

벡터 1개로 값을 갱신할 경우 변형된 값이 다음 수식에 반영될 수 있으므로 벡터 2개를 선언해서 옮겨줘야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<int> v(8);
    v[0] = 1;

    int N; cin >> N;

    while(N--) {
        vector<int> u(8);

        u[0] = v[1] + v[2];
        u[1] = v[0] + v[2] + v[3];
        u[2] = v[0] + v[1] + v[3] + v[4];
        u[3] = v[1] + v[2] + v[4] + v[5];
        u[4] = v[2] + v[3] + v[5] + v[6];
        u[5] = v[3] + v[4] + v[7];
        u[6] = v[4] + v[7];
        u[7] = v[5] + v[6];

        for(int i=0; i<8; i++) u[i] %= (int)(1e9 + 7);

        v = u;
    }

    cout << v[0] << "\n";
}

 

 

백준 BOJ 12026번 : BOJ 거리

문제 난이도 : Silver I

알고리즘 분류 : DP

 

앞에서부터 B, O, J, B, O, J, ... 순서로 문자를 골라 두 문자 사이의 거리가 x라면 그 비용이 x^2이라고 할 때 비용이 최소가 되도록 1 ~ N까지 선택했을 때 그 비용을 구하는 문제이다.

이동할 수 있는 가장 가까운 거리로 이동하는 그리디 풀이를 생각했으나 그렇게 할 경우 당연히도 N번째 칸에 도착하지 못하는 경우가 생긴다.

 

N ≤ 1000이므로 O(N^2) 풀이가 가능하다.

따라서 i를 이동시키면서 i보다 작은 모든 j에 대해 j → i의 이동을 검사할 수 있다.

 

dp[i]를 i번째 칸까지 이동하는데 걸리는 최소 비용이라고 가정하면, dp 값의 갱신을 위해 만족해야 하는 조건은 다음과 같다. (다음을 모두 만족해야 함)

1. B → O 또는 O → J 또는 J → B로의 이동

2. dp[j] 값이 -1이 아님

3. dp[i]값이 -1이거나 dp[i]보다 dp[j] + (i-j)*(i-j)가 더 작음

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    string str; cin >> str;

    vector<int> dp(N, -1);
    dp[0] = 0;

    for(int i=0; i<N; i++)
        for(int j=0; j<i; j++) {
            bool check = false;

            if(str[j] == 'B' && str[i] == 'O') check = true;
            if(str[j] == 'O' && str[i] == 'J') check = true;
            if(str[j] == 'J' && str[i] == 'B') check = true;

            if(!check || dp[j] == -1) continue;

            if(dp[i] == -1 || dp[j] + (i-j)*(i-j) < dp[i]) dp[i] = dp[j] + (i-j)*(i-j);
        }

    cout << dp[N-1] << "\n";
}

 

 

백준 BOJ 17216번 : 가장 큰 감소 부분 수열

문제 난이도 : Silver I

알고리즘 분류 : DP

 

주어진 수열에서 부분 수열을 골라 감소 수열이면서 그 합이 가장 큰 수열의 합을 구하는 문제이다.

 

어제 풀었던 문제이다.

N이 1000 이하이므로 이중 for문으로 검사하면서 DP로 구하면 되며, 어제 푼 문제에서 부등호만 바꿔줘도 되고 수열을 뒤집어 증가하는 부분 부열을 구해도 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    vector<int> dp(v);

    for(int i=0; i<N; i++)
        for(int j=0; j<i; j++)
            if(v[j] > v[i]) dp[i] = max(dp[i], dp[j] + v[i]);

    int ans = INT_MIN;
    for(int i=0; i<N; i++) ans = max(ans, dp[i]);

    cout << ans << "\n";
}

 

 

 

백준 BOJ 22869번 : 징검다리 건너기 (small)

문제 난이도 : Silver I

알고리즘 분류 : DP

 

i < j인 i번째 돌에서 j번째 돌로 이동할 때 (j - i) * (1 + |A_i - A_j|)만큼의 에너지가 필요하다고 할 때, 1번 돌에서 N번 돌까지 이동할 수 있는지를 구하는 문제이다.

N이 5000 이하이므로 이중 for문을 이용한 dp로 풀이할 수 있다.

 

이 때 dp는 int형이 아닌 단순 bool형으로 선언하여 이동할 수 있는지의 여부만 판단해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    vector<bool> dp(N, false);
    dp[0] = true;

    for(int i=0; i<N; i++)
        for(int j=0; j<i; j++) {
            if(!dp[j]) continue;
            if((i - j) * (1 + abs(v[i] - v[j])) <= M) dp[i] = true;
        }

    if(dp[N-1]) cout << "YES\n";
    else cout << "NO\n";
}

 

 

백준 BOJ 22871번 : 징검다리 건너기 (large)

문제 난이도 : Silver I

알고리즘 분류 : DP, 이분탐색

 

위의 문제에서 1번 돌에서 N번 돌까지 이동할 수 있는 최소 힘 K를 구하는 문제이다.

이는 단순 이분탐색으로 풀이할 수 있다. 양단 범위는 1과 INT_MAX로 잡으면 아주 충분하다.

 

위의 문제의 시간 복잡도는 O(N^2)라면, 이 문제의 시간 복잡도는 O(N^2 log K)가 된다. 이 때 K는 이분탐색을 할 양단 범위의 크기이다.

이분탐색은 범위를 잘못 잡거나 조건을 잘못 세우면 반례가 나올 수 있으니 조심하자.

나의 경우는 정형화 된 이분탐색 코드를 하나 정리해놓고 그대로 사용하여 푸는 방식을 사용한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    int l = 0, r = INT_MAX;

    while(l <= r) {
        int K = (l + r)/2;

        vector<bool> dp(N, false);
        dp[0] = true;

        for(int i=0; i<N; i++)
            for(int j=0; j<i; j++) {
                if(!dp[j]) continue;
                if((i - j) * (1 + abs(v[i] - v[j])) <= K) dp[i] = true;
            }

        if(dp[N-1]) r = K - 1;
        else l = K + 1;
    }

    cout << l << "\n";
}

 

 

백준 BOJ 13707번 : 합분해 2

문제 난이도 : Gold IV

알고리즘 분류 : DP, 조합론

 

0부터 N까지의 정수 K개를 더해서 합이 N이 되는 경우의 수를 구하는 문제이다.

이 때 한 개의 수를 여러 번 사용해도 되고 합의 순서가 다른 것은 다른 경우로 친다.

 

N과 K 모두 5,000 이하이므로 O(N^2)이나 O(NK)와 같은 시간 복잡도를 생각해볼 수 있겠다.

그렇다면 N 이하의 i에 대해, i 이하의 모든 j에 대해 점화식을 세우면 풀이할 수 있다.

 

dp[N][K]를 K개의 수를 사용하여 그 합을 N으로 만들 수 있는 경우의 수라고 하자.

그러면 점화식의 변수를 N에 대해서도 나타낼 수 있고 K에 대해서도 나타낼 수 있으므로 시간 복잡도가 O(N^2)보다 커진다. 이렇게 구하면 안된다.

 

문제 분류가 조합론이니 조합을 사용해서 특정 경우의 수를 O(1)에 구하는 방법을 생각해보자.

예제와 같이 N = 20, K = 2라면, 20개의 공을 1개의 막대를 이용해 2개의 덩어리로 나누면 된다.

N과 K에 일반화시켜보면 N개의 공을 K-1개의 막대를 이용해 K개의 덩어리로 나누면 된다. (이 경우의 수와 문제에서 요구하는 조건의 경우의 수와 일대일 대응이 된다.)

 

막대를 놓을 수 있는 위치의 수는 N+1개이고, 막대의 수는 K-1개이다.

각 막대는 구분이 되지 않고 한 위치에 여러 번 놓을 수 있으므로 (하나의 사이 공간에 막대가 2개가 위치한다는 것은 0을 의미함) 중복 조합을 사용하여 N+1 H K-1 = N+1+K-1-1 C K-1 = N+K-1 C K-1 = (N+K-1)! / (N! (K-1)!)이 된다.

 

그런데 이는 계산하기 복잡하므로 그냥 Combination에 대한 점화식 N C K = N-1 C K-1 + N-1 C K를 이용하여 답을 구하자.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

int dp[10001][5001] = {};
int mod = (int)(1e9);

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    for(int i=0; i<=N+M-1; i++) dp[i][0] = 1;
    for(int i=1; i<=N+M-1; i++)
        for(int j=1; j<=M-1; j++) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;

    cout << dp[N+M-1][M-1] << "\n";
}

 

N+K-1은 최대 9999까지 나올 수 있으므로 dp 배열의 크기를 잡을 때 조심해야한다.

배열 크기 잡을 때 크기가 무려 5,000만이라 긴가민가 했는데 메모리 계산을 해보지는 않았지만 놀랍게도 이게 돌아간다..

제출하면 정답 처리를 받을 수 있다.

 

 

백준 BOJ 1244번 : 스위치 켜고 끄기

문제 난이도 : Silver III

알고리즘 분류 : 구현

 

단순히 규칙에 따라 스위치를 켜고 꺼주기만 하면 되는 문제이다.

남학생은 자신의 번호의 배수의 번호의 전구를 toggle하고, 여학생은 자신의 번호를 기준으로 가장 긴 대칭 범위에 대해 스위치를 toggle 해주면 된다.

최종 스위치 상태를 출력할 때 20개씩 끊어서 출력해야하는 조건을 읽지 않으면 틀린다.. (이 문제의 정답률이 19%인 이유인 것 같다.)

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N+1);
    for(int i=1; i<=N; i++) cin >> v[i];

    int M; cin >> M;

    while(M--) {
        int a, b; cin >> a >> b;

        if(a == 1) {
            for(int i=b; i<=N; i+=b) {
                if(v[i] == 0) v[i] = 1;
                else if(v[i] == 1) v[i] = 0;
            }
        }
        else if(a == 2) {
            int l = b, r = b;

            while(v[l] == v[r] && l >= 1 && r <= N) l--, r++;

            for(int i=l+1; i<=r-1; i++) {
                if(v[i] == 0) v[i] = 1;
                else if(v[i] == 1) v[i] = 0;
            }
        }
    }

    for(int i=1; i<=N; i++) {
        cout << v[i] << " ";

        if(i % 20 == 0) cout << "\n";
    }
    cout << "\n";
}

 

 

백준 BOJ 10164번 : 격자상의 경로

문제 난이도 : Silver II

알고리즘 분류 : DP, 조합론

 

격자에서 길 찾는 문제이다.

0이 아닌 특정 칸이 K로 입력되었다면 그 칸은 반드시 지나야하고, 그렇지 않을 경우 단순히 왼쪽 맨 위에서 오른쪽 맨 아래까지 오른쪽, 아래로만 이동해서 도달할 수 있는 경우의 수를 구하는 문제이다.

예를 들어 (1, 1)에서 (5, 4)로 간다면 아래로 4번, 오른쪽으로 3번 가야하는데 이 순서가 바뀔 수 있으므로 4+3 C 4와 같이 계산할 수 있다.

 

만약 K != 0 즉 중간에 반드시 지나가는 칸이 존재한다면 "(1, 1)에서 K번째 칸까지 도달하는 경우의 수" × "K번째 칸에서 (N, M)까지 도달하는 경우의 수"와 같이 계산해주면 될 것이다.

Combination은 dp로 간단히 구할 수 있고 N+M ≤ 30이므로 long long을 사용해주면 되는데 그건 원래 #define int long long을 쓰고 있으므로 고려 안해줘도 된다.

 

K % M == 0인 경우를 주의해야 한다.

이를 한 번에 처리하기 위해 y = (K - 1) % M + 1과 같은 식을 이용했다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int dp[31][31] = {};

    for(int i=0; i<=30; i++) dp[i][0] = 1;
    for(int i=1; i<=30; i++)
        for(int j=1; j<=15; j++) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

    int N, M, K; cin >> N >> M >> K;

    if(K == 0) {
        int ans = dp[(N-1)+(M-1)][min(N-1, M-1)];

        cout << ans << "\n";
    }
    else if(K != 0) {
        int x = (K - 1) / M + 1;
        int y = (K - 1) % M + 1;

        int ans = dp[(x-1)+(y-1)][min(x-1, y-1)] * dp[(N-x)+(M-y)][min(N-x, M-y)];

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 6126번 : Cow Cash

문제 난이도 : Silver I (Silver II였는데 내가 투표해서 현재는 Silver I이다.)

알고리즘 분류 : DP, 배낭 문제

 

N가지 동전이 주어질 때 개수 제한없이 이들을 조합하여 M원을 만들 수 있는 방법의 수를 구하는 문제이다.

전형적인 knapsack 문제로, 특정한 점화식으로 풀린다.

각 화폐의 가치를 v[i]라고 할 때, 각 i에 대해 outer loop를 구성해주고 j=v[i] ~ M에 대해 dp[j] += dp[j - v[i]]로 반복문을 돌리면 경우의 수를 얻을 수 있다.

이에 대한 해설은 내가 이 링크에 노트 필기로 잘 정리해둔 적이 있으니 참고하길 바란다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    vector<int> dp(M+1);
    dp[0] = 1;

    for(int i=0; i<N; i++)
        for(int j=v[i]; j<=M; j++) dp[j] += dp[j - v[i]];

    cout << dp[M] << "\n";
}

 

 

여담이지만 백준 BOJ 2293번 : '동전 1', 백준 BOJ 9084번 : '동전'과 동일한 문제이다.

그래서 같은 난이도인 Gold V에 난이도 기여를 하기는 했는데, 범위가 다르거나 하여 다른 풀이가 존재한다던가, 아니면 웰노운이라 난이도를 낮춰야 한다면 투표를 수정하려고 한다.

---

 

결과 : 오늘도 10문제를 풀었다.