글 읽기 - 코드의 오류와 반례 혹시 알 수 있을까요...? ㅠㅠ

kim031504 3년 전 0

일단 check라는 변수를 매개변수로 넘겨 현재 어떤 숫자가 사용됐는지 판단해 중복을 막습니다.

또한, 0부터 시작하는 DFS와 9부터 시작해서 내려가는 DFS를 나누어

첫 번째로 부등호를 만족한 문자열에 도달하면 끝내는 방식으로 접근했습니다.

즉, 9부터 내려가는 for문에 의해 가장 처음으로 발견한 정답이 곧 최대,

0부터 시작해서 올라가는 for문에 의해 가장 처음으로 발견한 정답은 최소로 판단했습니다.

그런데 틀렸다고 나오네요 ㅠㅠ

혹시 제가 놓친 부분이 있을까요...?

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int K;
string minResult, maxResult;
vector<char> equalNums;
bool minFound = false;
bool maxFound = false;

// 부등호 관계가 옳은지 파악해주는 함수
bool isRightRelation(char equalNum, int n1, int n2) {
	if (equalNum == '<')
		return n1 < n2;
	else
		return n1 > n2;
}

void minDfs(string str, vector<bool> check) {
	if (minFound)
		return;

	int curLen = str.size();

	if (curLen == K + 1) {
		minResult = str;
		minFound = true;
		return;
	}

	char curEqualNum = equalNums[curLen - 1];
	int prevNum = (int)(str[curLen - 1] - '0');

	for (int num = 0; num < 10; num++) {
		if (minFound)
			return;

		if (check[num])
			continue;
		
		if (isRightRelation(curEqualNum, prevNum, num)) 
			minDfs(str + to_string(num), check);
	}
}

void maxDfs(string str, vector<bool> check) {
	if (maxFound)
		return;

	int curLen = str.size();

	if (curLen == K + 1) {
		maxResult = str;
		maxFound = true;
		return;
	}

	char curEqualNum = equalNums[curLen - 1];
	int prevNum = (int)(str[curLen - 1] - '0');

	for (int num = 9; num >= 0; num--) {
		if (maxFound)
			return;

		if (check[num])
			continue;

		if (isRightRelation(curEqualNum, prevNum, num))
			maxDfs(str + to_string(num), check);
	}
}

int main() {
	cin >> K;

	equalNums.resize(K);

	for (int k = 0; k < K; k++)
		cin >> equalNums[k];

	// 최소 결과 탐색
	for (int i = 0; i < 10; i++) {
		vector<bool> check;
		check.assign(10, false);

		check[i] = true;
		minDfs(to_string(i), check);
	}
	
	// 최대 결과 탐색
	for (int i = 9; i >= 0; i--) {
		vector<bool> check;
		check.assign(10, false);

		check[i] = true;
		maxDfs(to_string(i), check);
	}

	cout << maxResult << '\n';
	cout << minResult << '\n';

	return 0;
}

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

문제

문제

출처

ICPC

코드의 오류와 반례 혹시 알 수 있을까요...? ㅠㅠ

kim031504 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말