글 읽기 - 거의 마지막 테스트 케이스에서 틀린 것 같습니다.

akim9905 4년 전 0

반례나 문제가 뭔지 좀 알려주시면 감사하겠습니다ㅠ

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#define MAX 1001
using namespace std;

int dp[2][MAX * 100 + 1];
int a[MAX];
int b[MAX];

int main(){
    int t;
    scanf("%d", &t);

    while (t--){
        memset(dp, 0, sizeof(dp));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));

        int n;
        int sum = 0;

        scanf("%d", &n);

        for (int i = 1; i <= n; i++){
            scanf("%d %d", &a[i], &b[i]);
            sum += b[i];
        }

        int ans = INT_MAX;

        for (int i = 1; i <= n; i++){
            for (int j = 0; j <= MAX * 100; j++){
                if (j < a[i]){
                    dp[i % 2][j]= dp[(i - 1) % 2][j];
                }
                else {
                    int x = dp[(i - 1) % 2][j];
                    int y = dp[(i - 1) % 2][j - a[i]] + b[i];

                    dp[i % 2][j] = max(x, y);
                    ans = min(ans, max(j, sum - dp[i % 2][j]));
                }
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

dongpang 3년 전 0

ans는 모든 for문 안에서 dp[i % 2][j]가 구해질 때마다 갱신되어야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

거의 마지막 테스트 케이스에서 틀린 것 같습니다.

akim9905 4년 전 0

dongpang 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말