글 읽기 - 질문드립니다 (정답률 100%에서 틀림)

ssaico 6년 전 0

무엇이 문제일까요 ㅠㅠ

가장 먼저 무게 로 sort한 다음에 size로 비교해가며 다이나믹 프로그래밍으로 풀었습니다.

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct block{
    int height;
    int weight;
    int size;
    int idx;
}block;
typedef struct state{
    int preidx;
    int height;
    state(){
        preidx = 0;
        height = 0;
    }
}state;
 
bool cmp(block a, block b){
    return a.weight > b.weight;
}
 
int N;
state dp[101];
block input[101];
 
int main(void){
 
    scanf("%d", &N);
    for (int n = 1; n <= N; n++){
        scanf("%d %d %d", &input[n].size, &input[n].height, &input[n].weight);
        input[n].idx = n;
    }
 
    sort(input+1, input + N+1, cmp);
    for (int n = 1; n < N; n++){
        dp[n].height = input[n].height;
        dp[n].preidx = n;
    }
 
    int ansidx = 0;
    int ans= 0;
    for (int i = 1; i <= N; i++){
        for (int j = i+1; j <= N; j++){
            if (input[i].size >= input[j].size){//preidx = sort되고 나서
                if (dp[j].height < dp[i].height + input[j].height){
                    dp[j].height = dp[i].height + input[j].height;
                    dp[j].preidx = i;
                    if (ans < dp[j].height){
                        ans = dp[j].height;
                        ansidx = j;
                    }
                }
            }
        }
    }
    int cnt = 0;
    int sol[100];
    while (ansidx != dp[ansidx].preidx){
        sol[cnt++] = input[ansidx].idx;
        ansidx = dp[ansidx].preidx;
    }
    sol[cnt++] = input[ansidx].idx;
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++)printf("%d\n", sol[i]);
    return 0;
}

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

문제

문제

출처

ICPC

질문드립니다 (정답률 100%에서 틀림)

ssaico 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말