글 읽기 - 시간초과 질문 이왕 올리는 김에 하나 더요 2294번

meme0724 9년 전 0

앞에 올린거랑 이어서 이것도 시간초과가 뜨네요;;

n원을 만들려고 하고 그 방법이 f(n)가지라고 할때

동전의 종류가 k1, k2....kn개가 있으면

f(n-k1), f(n-k2),... 등을 먼저 구해서 f(n)의 최솟값을 구하는 방식으로 했는데

이것도 시간을 많이 잡아먹나 보네요...

ㅅ시간 안에 풀 수 있는 방법좀 가르쳐 주시면 감사하겠습니다!!

#include <stdio.h>

int a[100];
int min=100000000, ans=0;

void coin(int n, int k)
{
    if(k<0)
        return ;
    
    else if(k==0)
    {
        if (min > ans)
            min = ans;
    }
        
    else
    {
        for(int j=0; j<n; j++)
        {
            if(min > ans)
            {
	            ans++;
	    	   	coin(n, k-a[j]);
	            ans--;
            }
        }
    }
}
int main()
{
    int n,k,i;
    
    scanf("%d %d", &n, &k);
        
    for(i=0; i<n; i++)
        scanf("%d", &a[i]);
    
    coin(n,k);
    if( min==100000000 )
        printf("-1");
    else
	    printf("%d", min);
    
    return 0;
}

movie_jo 9년 전 1

만능링크

링크에 있는 피보나치 예제랑 비슷하게

f(n)을 구할 때 그 아래에 있는 이미 구한 f(n-k)들이 중복이 많아서 시간초과가 날거에요

그래서 한번 계산한 f(x)를 저장해놓고 불러내는 방식이 링크에 나옵니다!

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

문제

문제

출처

ICPC

시간초과 질문 이왕 올리는 김에 하나 더요 2294번

meme0724 9년 전 0

movie_jo 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말