글 읽기 - 어떤 부분에서 틀렸을까요?

unta 1년 전 0

배낭 문제에서 DP를 활용해 특정 아이템을 포함했을 때와 포함하지 않았을 때 최대 비용을 계산하는 것처럼, 특정 도시를 홍보하지 않을 때부터 최대한 홍보했을 때의 효과를 비교해 최댓값을 계산했습니다.

테스트 케이스 및 게시판의 반례는 통과함을 확인했는데 어떤 부분이 말썽일까요?

#include <stdio.h>
#include <stdlib.h>

int C, N;
int costs[20][2];
int dp[1001][20];

int solve(int current_cost, int city_index)
{
    // 가용한 비용이 0이거나 유효하지 않은 도시를 선택하면 0의 홍보 효과.
    if (current_cost == 0)
        return 0;
    if (city_index < 0)
        return 0;

    // DP로 이미 계산된 홍보 효과 반환.
    if (dp[current_cost][city_index] != 0)
        return dp[current_cost][city_index];

    // 현재 도시를 홍보하지 않는 경우부터 최대한 홍보했을 때의 효과를 계산하여 최댓값 반환.
    int max_value = 0;
    for (int n = 0; current_cost - n * costs[city_index][0] >= 0; n++)
    {
        int value = n * costs[city_index][1] + solve(current_cost - n * costs[city_index][0], city_index - 1);
        if (value > max_value)
            max_value = value;
    }

    return dp[current_cost][city_index] = max_value;
}

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

    for (int i = 0; i < 100; i++)
    {
        int promotion_effect = solve(i, N - 1);

        if (promotion_effect >= C)
        {
            printf("%d\n", i);
            break;
        }
    }

    return 0;
}

unta 1년 전 0

DP 배열의 크기를 잘못 잡아서 생긴 문제인 거 같습니다.

배열의 2차원 크기를 100001으로 잡으니 되더군요

그런데 다른 분들의 풀이와 좀 다른 접근이어서 비효율인 거 같습니다 ㅋㅋㅋㅋ

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

문제

문제

출처

ICPC

어떤 부분에서 틀렸을까요?

unta 1년 전 0

unta 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말