글 읽기 - 도와주세요!!

shsl119 7년 전 0

예제 돌려본결과 모두 맞게나오는데 뭐가문제일까요,....

배열만들어서 1개묶음부터~n개까지 채워가면서했는데,,,, 뭐가문제일까요 답답하내

#include<iostream>
#include<algorithm>
#define MAX 1001
using namespace std;


int main()
{
        int n;
        cin >> n;
        int price[MAX] = {0,};
        int arr[MAX][MAX] = {0,};
        int sum;
        for(int i=1;i<=n;i++)
        {
                cin>> price[i];
        }
        for(int i=1;i<=n;i++)
        {
                arr[1][i] = price[1]*i;
        }
        for(int i=2;i<=n;i++){
                for(int j=i;j<=n;j++){

                        sum = j;
                        int a = price[i]+arr[sum-i][sum-i];
                        int b = arr[i-1][j];
                        arr[i][j] = max(a,b);

                }
        }
        int max=0;
        for(int i=1;i<=n;i++){
                if(max<arr[i][n]) max = arr[i][n];
        }

        cout<<max<<endl;
        return 0;
}

nsy0042 7년 전 0

안녕하세요~

돌려본 결과 반례?를 찾은거 같은데

4 9 5 10 1일 경우

2개짜리 2번 사고 1개짜리 1번사면 9*2 + 4 = 22가 되며

돌린 값은 20이 나옵니다. 아마도 1개짜리 5번 사는걸로 인식이 되는거 같은데

최대값은 22이며 알고리즘쪽에서 뭔가 실수가 있으신 것 같네요.

shsl119 7년 전 0

감사합니다 반례덕에 해결했습니다 ㅋㅋ

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

문제

문제

출처

ICPC

도와주세요!!

shsl119 7년 전 0

nsy0042 7년 전 0

shsl119 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말