글 읽기 - 1943 번 반례좀 찾아주실 분 있으신것입니까?

pjjpark1 2년 전 0

다이나믹프로그래밍을 Top-down 방식으로 짰고 아이디어도 크게 문제가 없는거 같은데 어디서 문제가 생기는지 잘 모르겠습니다.

#include <iostream>
#include <cstring>

using namespace std;

int cache[100001];// 동적계획법 내용
int N;// 돈의 양 
int UseMoney[101];// 
int Moneylist[101];//

int SumMoney(int TMoney){
    if(TMoney<0)return 0;
    if(TMoney==0)return 1;
    int & ret=cache[TMoney];
    if(ret!=-1)return ret;
    ret=0;
    for(int i=0;i<N;++i){
        
        if(UseMoney[i]!=0){
        UseMoney[i]--;
        if(SumMoney(TMoney-Moneylist[i]))ret=1;
        UseMoney[i]++;
        }
    }
    //cout<< TMoney << " is "<< ret<<"\n";
    return ret;
}

int main()
{
    //일단 입력
    for(int i=0; i<3;i++){
        cin>> N;
        memset(cache,-1,sizeof(cache));
        int TotalM=0;
        for (int j=0; j<N;++j){
            cin>>Moneylist[j]>>UseMoney[j];
            TotalM+=Moneylist[j]*UseMoney[j];
        }
        cout<< SumMoney(TotalM/2)<<"\n";
    }
}

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

문제

문제

출처

ICPC

1943 번 반례좀 찾아주실 분 있으신것입니까?

pjjpark1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말