글 읽기 - 2294 동전2 메모리초과 질문입니다.

ljy8947 8년 전 0

메모리초과 이유를

구현은 너비우선 탐색을 하는데, 빠르게 하려고 내림차순으로 합니다.

그러다 정답을 만나면 바로 브레이크를 걸어서 시간을 단축시켰습니다.

#include <stdio.h>
#include <queue>
#include <algorithm>

int n, m, coin[101], ans=987654321, flag2;
struct VERTEX{ int money, cnt, flag; };
std::queue<VERTEX> Q;

bool compare(int a, int b)
{
    return a>b;
}

void solve()
{
    int a=0;
    Q.push( VERTEX{0, 0, 1} );
    VERTEX curr= Q.front();

    while(!Q.empty())
    {
        int i=0, flag2=1;
        VERTEX curr= Q.front();
        Q.pop();

        if(curr.money==m)
        {
            ans=curr.cnt;
            break;
        }
        for(i=0; curr.money+coin[a]*i<=m; i++);

        while(i>=0)
        {
            while(flag2==1)
            {
                Q.push( (VERTEX){curr.money+coin[a]*i, curr.cnt+i, 1} );
                if(i>0)
                    i--;
                flag2=0;
                break;
            }
            Q.push( (VERTEX){curr.money+coin[a]*i, curr.cnt+i, 0} );
            i--;
        }

        if(a<n-1 && curr.flag==1)
            a++;
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++)
        scanf("%d", &coin[i]);
    std::sort(coin, coin+n, compare);

    solve();
    printf("%d\n", ans-1);
    return 0;
}

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

문제

문제

출처

ICPC

2294 동전2 메모리초과 질문입니다.

ljy8947 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말