글 읽기 - 초기화값이 시간초과에 영향을 주는군요..

mic1021 7년 전 1

cache배열에는 동전갯수가 들어가는데 최대 금액이 10000이고 최대동전종류가 100개니까 1과 10000 사이의 숫자가 cache배열에 들어간다고 생각했습니다. 그래서 처음에 987654321로 초기화했는데 시간초과 받아서 혹시나 해서 -1로 했더니 맞았습니다... 오버플로우가 날 가능성도 없는데 말이죠..

#include <cstdio>
int n,coin[105],cache[10005];
int coin1(int sum){
        int i;
        if(sum==0) return 0;
        if(cache[sum]!=987654321) return cache[sum];
        for(i=0;i<n;++i) {
                if(sum>=coin[i] && cache[sum]>(coin1(sum-coin[i])+1)){
                        cache[sum]=(coin1(sum-coin[i])+1);
                }
        }
        return  cache[sum];
}
int main () {
        int i,k;
        scanf("%d %d",&n,&k);
        for(i=0;i<n;++i) scanf("%d",&coin[i]);
        for(i=0;i<10005;++i) cache[i]=987654321;
        coin1(k)!=987654321?printf("%d",coin1(k)):printf("%d",-1);
        return 0;
}
//위 코드는 시간초과 받은 코드
#include <cstdio>
int n,coin[105],cache[10005];
int coin1(int sum){
        int i;
        if(sum==0) return 0;
        if(cache[sum]!=-1) return cache[sum];
        cache[sum]=987654321;
        for(i=0;i<n;++i) {
                if(sum>=coin[i] && cache[sum]>(coin1(sum-coin[i])+1)){
                        cache[sum]=(coin1(sum-coin[i])+1);
                }
        }
        return cache[sum];
}
int main () {
        int i,k;
        scanf("%d %d",&n,&k);
        for(i=0;i<n;++i) scanf("%d",&coin[i]);
        for(i=0;i<10005;++i) cache[i]=-1;
        coin1(k)!=987654321?printf("%d",coin1(k)):printf("%d",-1);
        return 0;
}
//이 코드는 맞았습니다 뜬 코드

saeugsa_uka 7년 전 1

저도 cache를 987654321로 초기화 했는데 시간초과가 나서, 질문 게시판에서 현재 글을 확인하고 혹시나 해서 -1로 초기화 하고 돌렸더니 맞았네요...왜 그러는지 궁금하네요...

bok03220 5년 전 1

저도 이 문제로 고생하다가 틀린 이유를 알게 되어서 댓글 남깁니다.

틀린 이유는 "메모이제이션이 제대로 이루어지지 않기 때문입니다"

[맞는 코드]

if(cache[sum]!=-1) return cache[sum];

cache[sum]=987654321;

=> 여기서는 sum에 대해 계산을 해봤지만, 답을 구할 수 없는 경우 987654321로 cache값이 저장이 됩니다.

따라서 다음 번에 이 sum 인덱스에 대해 접근할 때, 이건 계산할 수 없는 값이구나 하고 if문에 걸려서 중복계산 없이 바로 cache[sum] (여기선 987654321이겠죠?)을 바로 반환합니다.

[틀린 코드]

if(cache[sum]!=987654321) return cache[sum];

=> 여기서는 cache[sum]을 다시 초기화해주는 코드가 없습니다.

따라서 방문했지만 답을 구할 수 없는 경우와, 방문을 아직 안해서 계산도 안한 경우의 cache값이 동일하게 됩니다.

결국 다음 번에 이 sum 인덱스에 접근했을 때, 이 sum은 계산해봐도 답을 구할 수 없는 값인지 알 수 없기 때문에 또 for문을 돌며 계산하게 됩니다.

그래서 시간 초과가 발생하게 됩니다.

hacastle 3년 전 0

@bok03220 설명 감사합니다. 많은 도움이 됐어요...!!!!

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

문제

문제

출처

ICPC

초기화값이 시간초과에 영향을 주는군요..

mic1021 7년 전 1

saeugsa_uka 7년 전 1

bok03220 5년 전 1

hacastle 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말