동적 계획법 2 / 백준

11066번 : 파일 합치기

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

문제 풀이

minCost[l][r]=l⋯rminCost[l][r] = l \cdots r

minCost[l][r]=mini=l⋯r−1(minCost[l][i]+minCost[i+1][r]+sum(l⋯r))minCost[l][r] = \underset{i = l \cdots r - 1}{min}(minCost[l][i] + minCost[i + 1][r] + sum_{(l \cdots r)})

minCost[501][501]minCost[501][501] 이나 minCost[500][500]minCost[500][500]이나 크기가 별 차이 없다고 생각해서 코드의 편의를 위해 처음에 전자의 방식으로 작성했었는데, 차이가 sizeof(int)×1001sizeof(int) \times 1001

Knuth's Optimization을 적용 가능한 문제이다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int T, K, file[500], sum[500], minCost[500][500] = {0, };
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &K);
        scanf("%d", &file[0]);
        sum[0] = file[0];
        for(int i = 1; i < K; i++) {
            scanf("%d", &file[i]);
            sum[i] = sum[i - 1] + file[i];
        }
        for(int gap = 1; gap < K; gap++)
            for(int l = 0; l + gap < K; l++) {
                int r = l + gap;
                int &ret = minCost[l][r] = 987654321;
                for(int i = l; i < r; i++)
                    ret = min(ret, minCost[l][i] + minCost[i + 1][r]);
                ret += sum[r];
                if(l > 0) ret -= sum[l - 1];
            }
        printf("%d\n", minCost[0][K - 1]);
    }
}

11049번 : 행렬 곱셈 순서

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

문제 풀이

C[l][r]=l⋯rC[l][r] = l \cdots r

C[l][r]=mini=l⋯r−1(C[l][i]+C[i+1][r]+matrix[l].first∗matrix[i].second∗matrix[r].second)C[l][r] = \underset{i = l \cdots r - 1}{min}(C[l][i] + C[i + 1][r] + matrix[l].first * matrix[i].second * matrix[r].second)

코드

#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
    int N, C[500][500] = {0, };
    pair<int, int> matrix[500];
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d %d", &matrix[i].first, &matrix[i].second);
    for(int gap = 1; gap < N; gap++)
        for(int l = 0; l + gap < N; l++) {
            int r = l + gap;
            int &ret = C[l][r] = (1 << 31) - 1;
            for(int i = l; i < r; i++)
                ret = min(ret, C[l][i] + C[i + 1][r] + matrix[l].first * matrix[i].second * matrix[r].second);
        }
    printf("%d", C[0][N - 1]);
}

1520번 : 내리막 길

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

문제 풀이

countPath(y,x)=[y,x]countPath(y, x) = [y, x]

[y2,x2][y2, x2]가 [y,x][y, x]에 인접한 정점이고, height[y2][x2]<height[y][x]height[y2][x2] < height[y][x]

코드

#include <cstdio>
#include <cstring>

int M, N, height[500][500], cache[500][500];
int d[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

int countPath(int y, int x) {
    if(y == M - 1 && x == N - 1) return 1;
    int &ret = cache[y][x];
    if(ret != -1) return ret;
    ret = 0;
    for(int i = 0; i < 4; i++) {
        int y2 = y + d[i][0], x2 = x + d[i][1];
        if(y2 < 0 || y2 >= M || x2 < 0 || x2 >= N) continue;
        if(height[y][x] > height[y2][x2])
            ret += countPath(y2, x2);
    }
    return ret;
}

int main() {
    scanf("%d %d", &M, &N);
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            scanf("%d", &height[i][j]);
    memset(cache, -1, sizeof(cache));
    printf("%d", countPath(0, 0));
}

10942번 : 팰린드롬?

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

문제 풀이

isP[l][r]=num[l⋯r]isP[l][r] = num[l \cdots r]

isP[l][r]=isP[l+1][r−1] && (num[l]==num[r])isP[l][r] = isP[l + 1][r - 1]\ \&\&\ (num[l] == num[r])

코드

#include <cstdio>

int N, M, num[2000];

bool isP[2000][2000];

int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d", &num[i]);

    for(int i = 0; i < N; i++) isP[i][i] = true;
    for(int i = 0; i < N - 1; i++) isP[i][i + 1] = (num[i] == num[i + 1]);
    for(int gap = 2; gap < N; gap++)
        for(int l = 0; l + gap < N; l++) {
            int r = l + gap;
            isP[l][r] = isP[l + 1][r - 1] && (num[l] == num[r]);
        }

    scanf("%d", &M);
    int l, r;
    for(int i = 0; i < M; i++) {
        scanf("%d %d", &l, &r);
        printf("%d\n", isP[l - 1][r - 1]);
    }
}

2629번 : 양팔 저울

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

문제 풀이

canCheck(i,w)=weight[i⋯ ]canCheck(i, w) = weight[i \cdots ]

1. i1.\ i번 추 사용 안할 때
canCheck(i,w) ∣=canCheck(i+1,w)canCheck(i, w)\ |= canCheck(i + 1, w)

w의 값은 구슬 무게가 1이고, 추의 무게 30개 모두 500일 때 최소값이 -14999이므로 cache배열에 접근할 때에는 14999를 더하여 접근하도록 하였다.

코드

#include <cstdio>
#include <cstring>

int weightNum, weight[30], marbleNum;

char cache[30][70000];

bool canCheck(int i, int w) {
    if(i == weightNum) return (w == 0);
    char &ret = cache[i][w + 14999];
    if(ret != -1) return ret;
    return ret = canCheck(i + 1, w) || canCheck(i + 1, w - weight[i]) || canCheck(i + 1, w + weight[i]);
}

int main() {
    scanf("%d", &weightNum);
    for(int i = 0; i < weightNum; i++)
        scanf("%d", &weight[i]);
    scanf("%d", &marbleNum);
    memset(cache, -1, sizeof(cache));
    for(int i = 0; i < marbleNum; i++) {
        int marble; scanf("%d", &marble);
        printf("%s ", canCheck(0, marble) ? "Y" : "N");
    }
}

2293번 : 동전 1

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

문제 풀이

cache[i][k]=1⋯icache[i][k] = 1 \cdots i

  1. i번째 동전을 사용하지 않고 채움
    cache[i][k]=cache[i−1][k]cache[i][k] = cache[i - 1][k]
  2. k>=coin[i]k >= coin[i]

반복적 동적 계획법을 작성할 때에는 꼭 슬라이딩 윈도 기법을 사용할 수 있는지 생각하자.
슬라이딩 윈도 기법을 사용할 때에는, cache 배열이 커지는 것에 대한 것을 생각하지 않아도 되므로 인덱스를 1부터 사용하여 기저사례를 처리하는 방식을 사용하기 용이하다.
따라서 cache배열이 커지는 것을 방지하기 위해 기저사례를 복잡하게 처리하는 방향으로 작성하지 않아도 된다는 것을 잊지 말고 있자.
슬라이딩 윈도를 아얘 1차원 배열에 덮어씌우는 형식으로 작성할 수도 있다.

슬라이딩 윈도를 더 이상 사용되지 않는 값을 버림으로써 공간 복잡도를 향상시키는 방법이라고 생각하자.

코드

#include <cstdio>

int main() {
    int n, k, coin[101], cache[2][10001] = {0, };
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d", &coin[i]);

    cache[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        cache[i % 2][0] = 1;
        for (int sum = 1; sum <= k; sum++) {
            cache[i % 2][sum] = cache[(i - 1) % 2][sum];
            if (sum >= coin[i])
                cache[i % 2][sum] += cache[i % 2][sum - coin[i]];
        }
    }

    printf("%d", cache[n % 2][k]);
}

// 1차원 배열 형태만으로 계산

#include <cstdio>

int main() {
    int n, k, coin[101], cache[10001] = {1, };
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d", &coin[i]);

    for(int i = 1; i <= n; i++)
        for (int sum = 1; sum <= k; sum++)
            if (sum >= coin[i])
                cache[sum] += cache[sum - coin[i]];

    printf("%d", cache[k]);
}

7579번 : 앱

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

문제 풀이

dp[idx][cost]=1⋯idp[idx][cost] = 1 \cdots i

  1. idx 앱 비활성화 안할 때
    dp[idx][cost]=dp[idx−1][cost]dp[idx][cost] = dp[idx - 1][cost]
  2. idx 앱 비활성화 할 때 (cost >= c[idx])
    dp[idx][cost]=dp[idx−1][cost−c[idx]]+m[idx]dp[idx][cost] = dp[idx - 1][cost - c[idx]] + m[idx]

슬라이딩 윈도 기법을 사용하였다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N, M, m[101], c[101], dp[10001] = {0, }, costSum = 0;
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= N; i++)
        scanf("%d", &m[i]);
    for(int i = 1; i <= N; i++) {
        scanf("%d", &c[i]);
        costSum += c[i];
    }
    for(int idx = 1; idx <= N; idx++)
        for(int cost = costSum; cost >= 1; cost--)
            if(cost >= c[idx])
                dp[cost] = max(dp[cost], dp[cost - c[idx]] + m[idx]);
    for(int cost = 1; cost <= costSum; cost++)
        if(dp[cost] >= M) {
            printf("%d", cost);
            break;
        }
    return 0;
}
[백준/자바스크립트(JavaScript)] 1931번: 회의실 배정
dev-server 핫리로드 설정 과정에서의 에러

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage