글 읽기 - (c언어) 반례도 해결했는데 어디가 문제인지 모르겠습니다;;

khs20130731 3년 전 0

동적계획법으로 풀었고 질문 게시판에 있는 반례들도 전부 맞게 출력하는데 틀렸다고 나옵니다.

혹시 어디가 문제인지 알 수 있을까요?

#include <stdio.h>
#include <string.h>

int weight[100];
int value[100];

int cache[100][100000];

int count(int n, int i, int k) {
    int result, tmp = 0;
    
    if (i == n-1) {
            return 0;
        else
            return value[i];
    }
        
    if (cache[i][k] != -1) return cache[i][k];
        
    result = count(n, i+1, k);
    if (weight[i] <= k) {
        tmp = count(n, i+1, k-weight[i]) + value[i];
        if (result < tmp) {
            result = tmp;
        }
    }
    
    return cache[i][k] = result;
}

int main(void) {
    int n, k;
    
    memset(cache, -1, sizeof(int)*100*10000);
    
    scanf("%d %d", &n, &k);
    for(int i=0; i<n; i++){
        scanf("%d %d", &weight[i], &value[i]);
    }
    
    printf("%d\n", count(n, 0, k));
}

p_ce1052 3년 전 0

풀었던 문제라 답해드리려고 들어왔다가 저도 30분 동안 갇혔네요 ㅋㅋ

1. 일단 12~16번째 줄은 코드가 잘리신 것 같습니다 컴파일이 안됩니다.

2. 그리고 캐시의 배열 크기가 부족합니다. k = 10만일 때 10만번째 인덱스가 있어야 하는데 캐시에는 99999번째 까지밖에 존재하지 않습니다. 그리고 캐시수를 늘린 만큼 memset도 다시 지정해야 하는데 그냥 sizeof(cache) 를 쓰시는걸 추천드립니다

khs20130731 3년 전 0

주석 쓴 부분 지우다가 코드가 일부 잘렸나보네요. 말씀해주신대로 캐시의 배열 크기를 조정하니까 바로 해결되었습니다.

감사합니다!!

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

문제

문제

출처

ICPC

(c언어) 반례도 해결했는데 어디가 문제인지 모르겠습니다;;

khs20130731 3년 전 0

p_ce1052 3년 전 0

khs20130731 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말