Rose   2년 전

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

d[i][state]= 

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

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

{

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

//솔루션:

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

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

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

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

namnamseo   2년 전

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

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

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

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

Rose   2년 전

정말 감사합니다.

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