글 읽기 - 반례가 있는데 어디서 잘못 접근했는지 모르겠습니다

wlsdndml213 2년 전 0

0번째 줄에 아무도 없다고 가정하고 1~N번째까지 학생수를 구하기위해

dp[row][bit] row번째 행의 학생의상태가 bit로 표현될 때 row+1줄부터 N번째 줄까지 학생수의 최댓값

을 이용하여 풀었습니다.

반례

1
3 3
x.x
x..
.x.

correct answer : 3인데 4로 출력됩니다. 어디서 잘못계산이 된걸까요

#include <iostream>
#include<queue>
#include<utility>
#include<string.h>
#define mp make_pair
#define pii pair<int,int>
using namespace std;
int T,N,M;
int barr[12]={0}; //입력된 'x', '.' 을 1,0으로 비트마스킹한 입력
int dp[12][1<<11]={0};  //row번째 행의 학생의 상태가 bit로 표현

//row번째 행의 학생의 상태가 bit 일때
//row+1번째 행부터 N번째 행까지 학생수의 최댓값
int solve(int row,int bit){ 

  if(row==N) return 0;  //N번째 행의 bit가 정해지면 끝이므로 0 반환
  int &ret=dp[row][bit];
  if(ret!=-1) return ret;
  ret=0;
  queue<pii> q; //현재bit와 1의개수를 저장한 pair
  q.push(mp(0,0));
  if((barr[row+1] & 1)!=0) //맨오른쪽자리가 x이면 학생 못앉음
    q.push(mp(1,1));
  int jari=1; //오른쪽부터 jari번째 자리를 검사
  // row+1줄에 앉을 학생의 상태비트를 만들기
  while(!q.empty() && jari<M){
    int qs=q.size();
    for(int i=0;i<qs;i++){
      pii deq=q.front();
      q.pop();
      q.push(deq);
      if((barr[row+1] & (1<<jari))==0) //자리가 x
        continue;
      if((jari>0 && bit & (1<<(jari-1))) !=0) //내 오른쪽앞 
        continue;
      if((jari<M && bit & (1<<(jari+1))) !=0) //내 left쪽앞 
        continue;
      if((deq.first & (1<<(jari-1)))==0){ //내 오른쪽자리가 비었으면
        q.push(mp(deq.first | (1<<jari),deq.second+1));
      }
    }
    jari++;
  }

  //jari==M
  //M번째 자리까지 검사함
  while(!q.empty()){ 
    pii deq=q.front();
    q.pop();
    ret=max(ret,solve(row+1,deq.first)+deq.second);
  }
  return ret;
}
int main() {
  cin>>T;
  while(T--){
    memset(barr,0,sizeof(barr));
    cin>>N>>M;
    char tmp;
    for(int i=1;i<=N;i++){
      int ex=1<<(M-1);
      for(int j=0;j<M;j++){
        cin>>tmp;
        barr[i]+=ex*(tmp=='.');
        ex/=2;
      }
    }
    memset(dp,-1,sizeof(dp));
    cout<<solve(0,0)<<endl; //0번째줄 아무도안앚음
  }
} 

wlsdndml213 2년 전 0

저처럼 푸신 분이 없겠지만.. 알려드리자면

22째줄에서 맨 오른쪽 자리가 비었다고 1을 넣으면 안되고 그 이전의 bit에서 왼쪽위에 자리까지 고려해주었어야합니다..

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

문제

문제

출처

ICPC

반례가 있는데 어디서 잘못 접근했는지 모르겠습니다

wlsdndml213 2년 전 0

wlsdndml213 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말