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

(追記) (追記ここまで)

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

1014번 - 컨닝

wlsdndml213 4년 전 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 4년 전 0

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

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

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

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

wlsdndml213 4년 전 0

wlsdndml213 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말