글 읽기 - 2091 문제의 테스트 케이스에 대해서 궁금한 점이 있습니다.

sodabori 3년 전 0

먼저 제가 작성하 코드는 따로 올려놨습니다. x를 구할 때는 -1이 가능한지 먼저 살피고 그 다음 -5, -10 -25를 살펴서 만약 해당 동전이 충분한 경우 dp에 저장된 -1,-5,-10,-25로부터 값을 그대로 들고 온 뒤 사용하고자 하는 동전에 대해서만 +1을 해주는 방식입니다. 현재 70%에서 답이 틀렸다고 뜨는데 아무리 생각해도 반례가 생각나지 않습니다. 그래서 원본 문제(https://contest.felk.cvut.cz/0...)의 반례를 구해보니 반례의 초반 40개를 확인해보고 70%에 해당하는 691 ~ 710까지를 확인했는데 틀린 경우가 하나도 없었습니다. 어떤 점이 잘못된걸까요? 그리고 어떤 반례가 있는 걸까요?

#include <stdio.h>

#define NUM_COINS 4
#define MAX_X 10000

int x;
int values[NUM_COINS] = {1, 5, 10, 25};
int coins[NUM_COINS];
int dp[NUM_COINS][MAX_X + 1] = {0};

bool is_valid(int x, int index) {
    int sum = 0;

    if (x - values[index] < 0) {
        return false;
    }

    if (dp[index][x - values[index]] >= coins[index]) {
        return false;
    }

    for (int i = 0; i < NUM_COINS; i++) {
        sum += dp[i][x - values[index]] * values[i];
    }

    if (sum != (x - values[index])) {
        return false;
    }

    return true;
}

int main() {
    scanf("%d", &x);
    for (int i = 0; i < NUM_COINS; i++) {
        scanf("%d", &coins[i]);
    }

    for (int i = 0; i <= x; i++) {
        for (int j = 0; j < NUM_COINS; j++) {
            if (is_valid(i, j)) {
                for (int k = 0; k < NUM_COINS; k++) {
                    dp[k][i] = dp[k][i - values[j]];
                }
                dp[j][i] += 1;
                break;
            }
        }
    }

    for (int i = 0; i < NUM_COINS; i++) {
        printf("%d ", dp[i][x]);
    }
    printf("\n");

    return 0;
}

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

문제

문제

출처

ICPC

2091 문제의 테스트 케이스에 대해서 궁금한 점이 있습니다.

sodabori 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말