글 읽기 - 컨닝 문제 기본DP 왜 틀린지 봐주세요! 반례모두만족

showmethemoney 5년 전 0

올라와 있는 반례는 모두 만족합니다.

(답이 안 맞는 반례가 있긴한데, 해당 반례를 정답코드에 넣어봐도 제 코드와 같은 답을 출력합니다.)

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

//컨닝

int C, N, M;
int board[10][10], cache[10][10]; // board 0_빈자리, 1_사람있음, -1_부숴짐
char line[10]; // 입력용

bool can_sit(int i, int j) { // 
	if(i-1>=0) {
		if(board[i-1][j]==1)
			return false;
		if(j-1>=0&&board[i-1][j-1]==1)
			return false;
	}
	if(i+1<N) {
		if(board[i+1][j]==1)
			return false;
		if(j-1>=0&&board[i+1][j-1]==1)
			return false;
	}
	return true;
}

int go() {
	int y = -1, x = -1;
	for(int j=0;j<M;j++) {
		for(int i=0;i<N;i++)
			if(!board[i][j]&&can_sit(i, j)) {
				x = i; y = j;
				break;
			}
		if(y!=-1)
			break;
	}
	if(y==-1) // 기저사례 : 더 앉힐 수 있는 자리가 없을 때
		return 0;
	
	int& ret = cache[x][y];
	if(ret != -1) return ret;
	
	board[x][y] = -1;
	ret = go(); // 앉히지 않았을 때
	
	board[x][y] = 1;
	ret = max(ret, 1 + go()); // 앉혔을 때
	
	board[x][y] = 0;
	
	return ret;
}

int main() {
	scanf("%d", &C);
	while(C--) {
		scanf("%d %d", &M, &N);
		memset(cache, -1, sizeof(cache));
		
		for(int j=0;j<M;j++) {
			scanf("%s", line);
			for(int i =0;i<N;i++)
				board[i][j] = -1 * (line[i] == 'x');
		}
		printf("%d\n", go());
	}
}

djm03178 5년 전 1

우선 각 줄의 최대 길이가 10이므로 %s로 입력받으려면 line은 최소 11칸이 있어야 합니다.

그를 제외해도, 많은 케이스에서 틀립니다. 과연 cache[x][y]에 기록해두는 것으로 충분할까요? 같은 자리를 방문해도, 이전 자리에서의 상태에 따라 결과가 달라질 수 있지 않을까요?

1
4 3
x.x
x..
.x.
.xx
output: 5
correct answer: 4

1
3 4
.x.x
.xx.
x.x.
output: 6
correct answer: 4

1
5 4
x.x.
.x.x
x.x.
x..x
..xx
output: 7
correct answer: 6

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

문제

문제

출처

ICPC

컨닝 문제 기본DP 왜 틀린지 봐주세요! 반례모두만족

showmethemoney 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말