글 읽기 - 조건에 대해서 이해가 안됩니다..

wldnjs3633 3년 전 0

소스코드에 대해선 생각해보고 다른분 들꺼 참고도 해서 작성을 했는데 계속 38퍼에서 틀리는 거에요

그래서 뭐가 다르지 하고 보니

DP 배열 설정할때 버틸수 있는 무게가 10만이라고 해서 처음에 DP[100][100000] 으로 했다가 안되서

다른분들이 DP[100][100010]으로 하셨길래 그렇게 바꿨더니 바로 되더라고요..

왜 100010으로 해야 하는지 이해가 안되서 그러는데 알려주실분 계신가요..

// Knapsack 문제의 경우, 그리디 보다는 DP 가 시간 복잡도가 더 낮다.( 그리디 : 2^n)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int,int>> bag;
//int dp[100][100000]={0,};            // 틀림
int dp[100][100010]={0,};
int maxvalue;

int main(void){
    int sizenum,sizeweight;
    cin>>sizenum>>sizeweight;

    // 데이터 입력
    int weight,value;
    for(int i=0;i<sizenum;i++){
        cin>>weight>>value;
        bag.push_back({weight,value});
    }

    // 정렬
    sort(bag.begin(),bag.end());

    // 초기값 설정 - dp[0][~]
    for(int i=0;i<sizeweight;i++){
        if(i>=bag[0].first-1) dp[0][i]=bag[0].second;
        else continue;
    }

    // DP 계산
    // DP[n][m] : 정렬한 가방 중 n번째 가방까지 고를때 무게가 m이 최대라면 가질 수 있는 최대가치값
    for(int i=1;i<sizenum;i++){
        for(int j=0;j<sizeweight;j++){
            // max 부분의 의미 : 이전 짐까지 들었을 때의 경우와 이 짐을 들 경우, 나머지 짐에 들어갈수 있는 짐의 최대 가치의 비교
            if(j>=bag[i].first-1) dp[i][j]=max(dp[i-1][j],dp[i-1][j-bag[i].first]+bag[i].second);
            else dp[i][j]=dp[i-1][j];
        }
    }

    cout<<dp[sizenum-1][sizeweight-1]<<"\n";

    return 0;
}

tor012 3년 전 1

테스트해보니 꼭 100010 은 아니고 100001 칸 이상이면 되는듯합니다.

로직을 파악해본것은 아니기에 딱 100000에 대당하는 인덱스를 접근하는 일이 있는 듯 하고, 해당 경우에서 틀렸습니다를 받지 않을까 예상해봅니다.

그러므로 100000 인덱스가 생길 수 있도록 100001 칸 이상 잡아주는 듯 합니다.

(보통 이러한 상황에서 인덱스초과에 대한 문제를 방지하기위해 메모리가 넉넉하다면 좀더 많은 공간을 그냥 잡아주는 경우가 많습니다.)

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

문제

문제

출처

ICPC

조건에 대해서 이해가 안됩니다..

wldnjs3633 3년 전 0

tor012 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말