글 읽기 - 일차원배열로 구현해보다가 .. 반례를 찾고싶습니다 (C++)

flpdsc 2년 전 0

약간 어거지로 풀었는데

반례를 찾고싶습니다 ㅠㅠ

#include <iostream>
using namespace std;

int V[50], DP[1001];

int main()
{
    int n, s, m;
    cin >> n >> s >> m;
    for(int i=0; i<n; ++i)
        cin >> V[i];

    if(s+V[0]<=m) DP[s+V[0]] = 1;
    if(s-V[0]>=0) DP[s-V[0]] = 1;

    for(int i=1; i<n; ++i){
        for(int j=m; j>=0; --j){
            if(DP[j]==i){
                if(j-V[i]>=0) DP[j-V[i]] = i+1;
                if(j+V[i]<=m) DP[j+V[i]] = i+1;
            }
        }
    }

    for(int i=m; i>=0; --i){
        if(DP[i]==n){
            cout << i << '\n';
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}

djs100201 2년 전 1

dp가 2차원이거나 최소 이전거를 전부 저장한채로 들고다녀야 할 거 같습니다.

보통 2차원 dp를 1차원으로 반복문의 순서를 뒤집어 줄일때는 참조하는 index가 i>j등의 성질이 성립해야 합니다.

그걸 염두해서 j를 m부터 0까지 줄여나가신거 같은데, 이 문제는 j-V[i] j+v[i] 즉, 큰 쪽 작은쪽 모두 참조하기 때문에 단순히 j를 줄이는 방식으로는 해결하기 어렵습니다.

flpdsc 2년 전 0

이해하는데 도움이 됐습니다! 감사합니다.

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

문제

문제

출처

ICPC

일차원배열로 구현해보다가 .. 반례를 찾고싶습니다 (C++)

flpdsc 2년 전 0

djs100201 2년 전 1

flpdsc 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말