글 읽기 - 양팔저울 문제 답답합니다 반례나 틀린점 알려주실분있을까요

sontg123 3년 전 0

일단 게시판에 있는 건 다 되는것 같습니다

추의개수x15000까지만 2차원 벡터 잡아서 dp를 썻습니다

최대추 무게가500이고 30개 니까 15000까지만 잡았고 15000이상 무게를 재려고 하면 무조건 N나오게 했습니다

추의 idx를 증가시키면서 이전에 잴 수 있다고 한 부분들 체크해논것 + 체크한곳 +- 추의무게(절대값),자신의추의무게 체크해 가면서 dp 채웟고요

뭐가 틀렸는지 원 ㅠㅠ

#include <iostream>
#include <vector>
using namespace std;
class balance{
private:
    vector<int> map;
    vector<vector<bool>> dp;
    int N,SUM;
public:
    balance(int n):N(n){
        map.resize(n+1,0);
        dp.resize(n+1);
        for(int i=0;i<=N;i++)
            dp[i].resize(15001,false);
    
    };
    void set_val(){
        int sum=0;
        for(int i=1;i<=N;i++){
            std::cin >>map[i];
            sum+=map[i];
        }
        SUM=sum;
    }

    void knapsack(){
        int sum=0;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=sum;j++){
                dp[i][j]=dp[i-1][j];
            }
            for(int j=1;j<=sum;j++){
                if(dp[i][j]){
                    dp[i][j+map[i]]=true;
                    dp[i][abs(j-map[i])]=true;
                }
            }
            dp[i][map[i]]=true;
            sum+=map[i];
        }
    }

    void print_dp(){
        std::cout <<'\n';
        for(int i=1;i<=N;i++){
            for(int j=1;j<=SUM;j++)
                std::cout <<dp[i][j] << ' ';
            std::cout << '\n';
        }
    }

    void find(int n){
        if(n>15000||n<=0)
            std::cout <<'N';
        else if(dp[N][n]==true)
            std::cout<<'Y';
        else
            std::cout<<'N';
    }

};
int main(){
    int n,tmp;
    std::cin >>n;
    balance b(n);
    b.set_val();
    b.knapsack();
    std::cin >> n;
    for(int i=0;i<n;i++){
        std::cin >> tmp;
        b.find(tmp);
        if(n!=n-1)
            std::cout << ' ';
    }

    return 0;
}

jjang36524 3년 전 0

n이 15000보다 크면 N이 두번 출력됩니다.

sontg123 3년 전 0

아 그쪽 수정 했었는데 ㅜㅜ 아니네요 왜틀리는거지 지금 6번째실패중 흑흑..

sontg123 3년 전 1

각종 시도끝에 13번제출만에 통과하고 글을 남깁니다

알고리즘 부분은 달라진거 없는데 메모리부분이 문제였나봅니다 dp의 2차원 vector를 처음 class생성할 때 15001개 할당해주고 시작했는데

값을 다 받은 후 모든 값의 합 만큼만 할당해줬더니 통과를 합니다..

왜그런건지 모르겟네요 ㅠㅠ일단 통과코드는 공유합니다

#include <iostream>
#include <vector>
using namespace std;
class balance{
private:
    vector<int> map;
    vector<vector<int>> dp;
    int N,SUM;
public:
    balance(int n):N(n){
        map.resize(n+1,0);
        dp.resize(n+1);
    };
    void set_val(){
        int sum=0;
        for(int i=1;i<=N;i++){
            std::cin >>map[i];
            sum+=map[i];
        }
        SUM=sum;
        for(int i=0;i<=N;i++)
            dp[i].resize(SUM+1);
    }

    void knapsack(){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=SUM;j++){
                if(dp[i-1][j]){
                    dp[i][j]=true;
                    dp[i][j+map[i]]=true;
                    dp[i][abs(j-map[i])]=true;
                }
            }
            dp[i][map[i]]=true;
        }
    }

    void print_dp(){
        std::cout <<'\n';
        for(int i=1;i<=N;i++){
            for(int j=1;j<=SUM;j++)
                std::cout <<dp[i][j] << ' ';
            std::cout << '\n';
        }
    }

    void find(int n){
        if(n>SUM||n<=0){
            std::cout <<'N';
            return ;
        }
        if(dp[N][n]==true)
            std::cout<<'Y';
        else
            std::cout<<'N';
    }

};
int main(){
    int n,tmp;
    std::cin >>n;
    balance b(n);
    b.set_val();
    b.knapsack();
    std::cin >> n;
    for(int i=0;i<n;i++){
        std::cin >> tmp;
        b.find(tmp);
        if(i!=n-1)
            std::cout << ' ';
    }
  

    return 0;
}

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

문제

문제

출처

ICPC

양팔저울 문제 답답합니다 반례나 틀린점 알려주실분있을까요

sontg123 3년 전 0

jjang36524 3년 전 0

sontg123 3년 전 0

sontg123 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말