글 읽기 - 왜 시간초과가 나올까요,,?

dldngud97 2년 전 0

백트랙킹 문제라 생각하고 풀었는데

7%대에서 시간초과가 나오네요,,

어떤 이유로 시간초과가 나오는지 잘 모르겠습니다,,ㅠㅠ

#include <iostream>
#include <algorithm>

using namespace std;

int n, k, maxV(0);
pair<int, int> WV[101];

void getMax(int m, int v, int w) // m은 현재 index, v는 지금까지의 가치의 합, w는 배낭에 남은 무게
{
    if(m > n) // m은 현재 인덱스이고 m이 n을 넘어가면 종료
        return;
    for(int i = m; i <= n; i++)
    {
        int curW = w - WV[i].first;
        if(curW < 0) // 남은 무게에서 i번째 물건의 무게를 뺀 값이 음수가 나오면 종료
            return;
        int curV = v +  WV[i].second;
        if(maxV < curV) // i번째 물건의 가치를 더한 값이 maxV보다 크면 갱신
            maxV = curV;
        getMax(i + 1, curV, curW);
    }
}

bool cmp(pair<int, int> x, pair<int, int> y)
{
    return x.first > y.first;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) // n은 1부터 시작
    {
        int w, v;
        cin >> w >> v;
        WV[i].first = w;
        WV[i].second = v;
    }
    sort(WV + 1, WV + (n + 1), cmp); // 무게를 기준으로 내림차순 정렬
    getMax(1, 0, k);
    cout << maxV << "\n";
}

djs100201 2년 전 1

애초에 백트래킹으로 풀 수 있는 시간복잡도가 아닙니다.
다른 방법을 생각해 보세요!

dldngud97 2년 전 0

아항,,, 시작부터가 잘못되었나보네요

감사합니다!!

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

문제

문제

출처

ICPC

왜 시간초과가 나올까요,,?

dldngud97 2년 전 0

djs100201 2년 전 1

dldngud97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말