글 읽기 - 문제의 예외가 어디서 발생하는지 알 수가 없습니다.

gon109 4년 전 0

정답체크가 80퍼센트에서 틀렸습니다로 뜨네요. 다른분들 중에서도 80퍼센트에서 오답처리 되시는 분들이

있다고 질문 올리셨는데, 저도 마찬가지로 어디가 문제인지 모르겠습니다...;<--공지에서 퍼센트 언급해봤자 의미없다고 하신건 알고있습니다...

예제는 완벽하게 돌아가고, 코드도 제시한 조건들을 모두 고려한 것 같은데도 자꾸 오답이 뜨는데

혹시 dp코드의 로직이 잘못된 걸까요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include <algorithm>
#include <cstring> //memset
#include<tuple>
#include<functional>
#include<map>
using namespace std;

//행, 열, 인덱스
int cache[10][10][20];
vector<string> word;
int wordlen;
string board[6];

int dy[8] = { -1,-1,-1,0,1,1,1,0 };
int dx[8] = { -1,0,1,1,1,0,-1,-1 };

//동적계획법으로 단어탐색 구현.
int find_str(int y, int x, int index, int k) {
	int next = index + 1;
	//0~n-1까지가 word이므로 다음 index가 wordlen과 같으면 종료.
	if (next >= wordlen) {
		return 1;
	}
	for (int dr = 0; dr < 8; dr++) {
		int ny = y + dy[dr];
		int nx = x + dx[dr];
		//보드 범위안에서, 방문안했고 보드의 다음글자와 이동시 일치하는 경우.
		if ((0 <= ny && ny < 4 && 0 <= x && x < 4)) {
			if ((cache[ny][nx][next] == 1) && (board[ny][nx] == word[k][next])) {
				if (find_str(ny, nx, next, k) == 1) {
					return 1;
				}
			}
		}
	}
	cache[y][x][index] = 0;
	return 0;
}

int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		word.push_back(s);
	}
	//사전순 정렬.
	sort(word.begin(), word.end());
	
	int cases;
	cin >> cases;
	while (cases--) {
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 20; k++)
					cache[i][j][k] = 1;
			}
		}
		for (int i = 0; i < 4; i++) {
			cin >> board[i];
		}

		string longword = "";
		int find_cnt = 0;
		int tot_score = 0;
		for (int k = 0; k < n; k++) {
			bool escape = false;
			wordlen = word[k].length();
            //단어는 최대 8글자.
			if (wordlen > 8) continue;
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					//보드에서 단어의 첫글자를 찾고, find_str값이 1인경우(보드에서 단어를 찾은경우)
					if (board[i][j] == word[k][0] && (find_str(i, j, 0, k) == 1)) {
						escape = true;
						find_cnt++;
						if (wordlen == 3 || wordlen == 4) tot_score += 1;
						else if (wordlen == 5) tot_score += 2;
						else if (wordlen == 6) tot_score += 3;
						else if (wordlen == 7) tot_score += 5;
						else if (wordlen == 8) tot_score += 11;
						//사전순 정렬했으므로 길이가 갱신될때만 longword를 갱신
						if (wordlen > longword.length()) {
							longword = word[k];
						}
					}
					if (escape)break;
				}
				if (escape)break;
			}
		}

		cout << tot_score << " " << longword << " " << find_cnt << "\n";
	}


	return 0;
}

gon109 4년 전 3

dp로 쓰는경우

1
ABA

ABCD
EFGH
IJKL
MNOP
인 보드에서 ABA를 찾았다고 나오네요. 칸을 다시 못밟게 처리해줘야되는게 문제였네요 ㅠㅠ

dbfldkfdbgml 2년 전 1

다음 반례로 수정합니다

1
ABA 

1
ABCD
EFGH
IJKL
MNOP
정답 0 0

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

문제

문제

출처

ICPC

문제의 예외가 어디서 발생하는지 알 수가 없습니다.

gon109 4년 전 0

gon109 4년 전 3

dbfldkfdbgml 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말