글 읽기 - 동적계획법으로 풀었는데 어디가 잘못됬을까요...

corona10 8년 전 0

테스트 케이스는 통과를 하는데 오답이라고 하네요. 지적부탁드립니다

접근방법은 주석에 적었습니다..

#include <iostream>
#include <cstring>

constexpr int N = 10001;
constexpr int U = 6;

using namespace std;

int dp[N][U] = {0,};
int equipment[N][U] = {0, };
bool choosen[N] = {false,};

int calculate(int n, int k);
void score(int* item, int& score);

int main()
{
    int t = 0;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        memset(dp, 0, sizeof(int)*N*U);
        memset(equipment, 0, sizeof(int)*N*U);
        memset(choosen, false, sizeof(bool)*N);
        int n, k;
        cin >> n >> k;
        for(int j = 1; j <= n; j++)
        {
            cin>>equipment[j][1];
            cin>>equipment[j][2];
            cin>>equipment[j][3];
            cin>>equipment[j][4];
            cin>>equipment[j][5];
        }
        cout<<calculate(n, k)<<endl;
    }
    return 0;
}

void score(int* item, int& score)
{
    int sc = 0;
    for(int i = 1; i <U; i++)
    {
        sc += item[i];
    }
    score = sc;
}

int calculate(int n, int k)
{
    int answer = 0;
    /**
     n개를 골랐을 때 각 능력치별 점수는
     dp[n][1], dp[n][2], .... dp[n][5]
     따라서 dp[n][1] = max(dp[n-1][1], equipment[j][1])
     ==> n개 골랐을 때 첫번째 능력치의 최대치는 (n-1개 골랐을 때 첫번째 능력치의 최대치, j번째 장비의 첫번째 능력치) 중 최대치이다.
     ==> 따라서 dp[n]이 될수 있는 건 dp[n-1] + j번째 장비를 골랐을 때 최대 점수가 되는 것 이다.
     **/
    for(int i = 1; i <= k; i++)
    {
        int max_score = 0;
        for(int j =1; j <= n; j++)
        {
            if(choosen[j] != true)
            {
                int temp[U] = {0,};
                temp[1] = max(dp[i-1][1], equipment[j][1]);
                temp[2] = max(dp[i-1][2], equipment[j][2]);
                temp[3] = max(dp[i-1][3], equipment[j][3]);
                temp[4] = max(dp[i-1][4], equipment[j][4]);
                temp[5] = max(dp[i-1][5], equipment[j][5]);
                int temp_score = 0;
                score(temp, temp_score);
                if(temp_score > max_score)
                {
                    max_score = temp_score;
                    dp[i][1] = temp[1];
                    dp[i][2] = temp[2];
                    dp[i][3] = temp[3];
                    dp[i][4] = temp[4];
                    dp[i][5] = temp[5];
                    answer = temp_score;
                    choosen[j] = true;
                }
            }
        }
    }
    return answer;
}

amok 8년 전 1

반갑습니다. 같은 학교 다니네요.

접근 방법이 완전히 잘못되었습니다.

1
3 2
10 10 0 0 0
12 0 0 0 0
0 12 0 0 0

를 입력으로 넣어보세요.

총 K번의 각각의 선택마다 점수를 최대화하려 하는데, 동적 계획법보다는 그리디라고 할 만한 방법인 것 같네요.

또 하나 보이는 문제점은 chosen[j] 를 true로 만든 후 이전에 true로 만들었던 chosen을 가만히 둔다는 것인데, 다음 입력을 넣어보세요. 이건 비교적 사소한 문제점인데, 이걸 고친다고 문제가 해결되는 것은 아닙니다만...

1
5 5
10 0 0 0 0
0 11 0 0 0
0 0 12 0 0
0 0 0 13 0
0 0 0 0 14

힌트를 드리자면, 예를 들어 N개의 장비 중에서 3개를 고른다고 할 때, 최종 장비의 합성 점수가 (a, b, c, d, e) 라고 합시다. 이 최종 합성 점수에서, a, b, c, d, e는 각각 적당한 장비의 점수였을 텐데, a는 10번 장비의 점수, b와 d는 89번 장비의 점수 c는 5번 장비의 점수, e는 65번 장비의 점수와 같이 되는 것은 불가능합니다. 우리는 장비 최대 3개를 합성했으니까요. a, b 는 45번 장비의 점수, c, d는 67번 장비의 점수, e는 90번 장비의 점수처럼 되는 경우는 가능합니다. 만약 우리가 a와 b가 같은 장비의 점수에서 나오는 것을 안다면, O(N)의 스캔으로 a+b을 최대화하는 장비를 알아낼 수 있겠죠.

구현이 상당히 까다롭습니다.

corona10 8년 전 0

@amok님 주신 힌트로 다시 한번 문제 풀어봐야겠네요. 정말로 감사드립니다.

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

문제

문제

출처

ICPC

동적계획법으로 풀었는데 어디가 잘못됬을까요...

corona10 8년 전 0

amok 8년 전 1

amok 8년 전 2

corona10 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말