글 읽기 - 답변 부탁드리겠습니다

Rose 5년 전 0

일단 dp 배열 2개로 상태를 표시하였구요,

d[i][state]=

{

state:0 : 현재 파티에서 거짓말을 했을시 현재까지 할수있는 최대 거짓말

state:1 : 현재 파티에서 참말을 했을시 현재까지 할수있는 최대 거짓말

{

know[i][state][j]= d배열이 d[i][state]상태일때 j사람이 알고있는 사실(0: 거짓말, 1: 참말, -1: 아무것도 모르는 상태)

//솔루션:

1. 첫번째 파티에서 참말을 했을시와 거짓말이 가능할때, 거짓말을 했을때를 먼저 지정해준다.

2. 자기 이전 배열(d[i-1][state]) 을 참고하여 만약 현재 파티에서 거짓말을 할수 있다면( know 배열을 참고하여 ) 거짓말을 했을시와 참말을 했을시를 각각 구해준다.

혹시 제 솔루션에 문제가 있는건가요?? 아님 그냥 구현을 잘못한걸까요??

(질문게시판의 모든 예제 다넣어보아도 정상적으로 돌아가는거 확인하였습니다.)

#include<stdio.h>
#include<vector>
using namespace std;
vector<int> present[54];
int d[54][2];
int know[54][2][54];//d[i][state]상태일때 j사람이 알고있는 정보(1: 진실 0:거짓 -1:아무것도 안들은 상태)
int truth[54];
int Max(int a,int b){ return (a<b)?b:a; }
int main(){
    int n,m,tr;
    scanf("%d %d",&n,&m);
    scanf("%d",&tr);
    for(int i=0;i<tr;i++){
        int x;
        scanf("%d",&x);
        truth[x]=1;
    }
    for(int i=0;i<m;i++){
        int p;
        scanf("%d",&p);
        for(int j=0;j<p;j++){
            int x;
            scanf("%d",&x);
            present[i].push_back(x);
        }
        for(int j=1;j<=n;j++){
           if(truth[j]) know[i][0][j]=know[i][1][j]=truth[j];
           else know[i][0][j]=know[i][1][j]=-1;
        }
        d[i][0]=d[i][1]=-1;
    }
    int t;
    for(t=0;t<present[0].size();t++){
        if(truth[present[0][t]]==1)
            break;
    }
    if(t==present[0].size()){
        d[0][0]=1;
        for(int i=0;i<present[0].size();i++)
            know[0][0][present[0][i]]=0;
    }
    d[0][1]=0;
    for(int i=0;i<present[0].size();i++){
        know[0][1][present[0][i]]=1;
    }
    for(int i=1;i<m;i++){
        int j;
        for(int tw=0;tw<=1;tw++){
            if(d[i-1][tw]!=-1){
                for(j=0;j<present[i].size();j++){
                    if(know[i-1][tw][present[i][j]]==1){
                        break;
                    }
                }
                if(j==present[i].size()){
                    if(d[i][0]<d[i-1][tw]+1){
                        d[i][0]=d[i-1][tw]+1;
                        for(j=1;j<=n;j++){
                            know[i][0][j]=know[i-1][tw][j];
                        }
                        for(j=0;j<present[i].size();j++){
                            know[i][0][present[i][j]]=0;
                        }
                    }
                }
            }
        }
        for(int tw=0;tw<=1;tw++){
            if(d[i-1][tw]!=-1){
                for(j=0;j<present[i].size();j++){
                    if(know[i-1][tw][present[i][j]]==0){
                        break;
                    }
                }
                if(j==present[i].size()){
                    if(d[i][1]<d[i-1][tw]){
                        d[i][1]=d[i-1][tw];
                        for(j=1;j<=n;j++){
                            know[i][1][j]=know[i-1][tw][j];
                        }
                        for(j=0;j<present[i].size();j++){
                            know[i][1][present[i][j]]=1;
                        }
                    }
                }
            }
        }
    }
    printf("%d",Max(0,Max(d[m-1][0],d[m-1][1])));
    return 0;
}

know 값의 정의를 저렇게 해서 잘 작동할지 모르겠어요.

i번째 파티에서 거짓말을 했는지의 여부가 state와 같을 때, 할 수 있는 최대 거짓말의 갯수가 dp[i][state]에 저장되어있고,
바로 그 때 각각의 사람들이 알고 있는지의 여부가 know[i][state][...]에 적혀 있는데요,

딱 dp[i][state]개의 거짓말을 하는 방법이 굉장히 여러 가지가 있을 수 있고,
그중에 딱 한 가지 경우(dp[i-1][...]에서 넘어온 경우)만 know에 적어놓고 사용하고 있잖아요??

적어놓은 그 know값을 사용해서 그 뒤의 값들도 구해 나가는게
항상 최적일까요...?
저는 그렇지 않을 것 같아요ㅠㅠ

Rose 5년 전 0

정말 감사합니다.

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

문제

문제

출처

ICPC

답변 부탁드리겠습니다

Rose 5년 전 0

namnamseo 5년 전 0

Rose 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말