글 읽기 - 예제는 맞는데 왜틀렸는지 모르겠습니다

gdlife 5년 전 0

먼저 문제 접근은 재귀로 탐색하였습니다.

모든 경우를 다 찾아서 값을 비교하지 않고,

최대값의 경우 9부터시작해서 앞자리부터 채우면서 가능하면 뒷자리로 넘어가고, 안되면 다시 앞자리로 넘어오는 방식으로 햇고,

최소값의 경우는 반대로 0부터 시작했습니다.

예제 테케와 문제 설명에 참조된 부등호 9개 짜리를 테스트한 경우 맞습니다.

최대와 최소가 같을 경우도 마찬가지로 똑같이 나옵니다. (<<<<<<<<< 경우)

제출하면 그냥 처음부터 틀렸다고 나오는데 반례나 문제점을 알 수 있을까요??

#include<stdio.h>

int n;
char op[10], check[10]; //부등호, 숫자체크
char a[13], b[13];//최대값,최소값
int tmp[13]; //재귀로 만든 숫자가 들어갈 배열
bool f(int now, int flag, int back_flag) //현재 위치, 최대값최소 flag,다시 이전자릿수로 넘어가야 하는 경우를 나타내는 변수
{
	if (now < 1)return 0; //처음으로 오면 못 찾고 종료

	if (now >= n + 1)return 1; //부등호 만족하는 n+1자리 숫자 찾음
	if (flag) ///최대값
	{
		for (int i = 9; i >= 0; i--) //9부터 시작
		{
			if (op[now - 1] == '<' && !check[i] && tmp[now - 1] < i)
			{
				if (back_flag) //자릿수를 뒤로 이동한 만큼 해당 체크배열 초기화
				{
					for (int k = 0; k<back_flag; k++)
						check[tmp[now + k]] = false;
				}
				tmp[now] = i; //현재 위치에 숫자대입
				check[i] = true;
				return f(now + 1, flag, 0); 
			}
			else if (op[now - 1] == '>' && !check[i] && tmp[now - 1] > i)
			{
				if (back_flag)
				{
					for (int k = 0; k<back_flag; k++)
						check[tmp[now + k]] = false;
				}
				check[i] = true;
				tmp[now] = i;
				return f(now + 1, flag, 0);
			}
		}
	}
	else if (flag == 0) //최소값 찾는경우
	{
		for (int i = 0; i<10; i++) //0부터 시작해서 탐색
		{
			if (op[now - 1] == '<' && !check[i] && tmp[now - 1] < i)
			{
				if (back_flag)
				{
					for (int k = 0; k<back_flag; k++)
						check[tmp[now + k]] = false;
				}
				tmp[now] = i;//첫자리 대입
				check[i] = true;
				return f(now + 1, flag, 0);
			}
			else if (op[now - 1] == '>' && !check[i] && tmp[now - 1] > i)
			{
				if (back_flag)
				{
					for (int k = 0; k<back_flag; k++)
						check[tmp[now + k]] = false;
				}

				check[i] = true;
				tmp[now] = i;//첫자리 대입
				return f(now + 1, flag, 0);
			}
		}
	}
	return f(now - 1, flag, back_flag + 1);//현재 위치에 들어갈 숫자를 찾지못한 경우 다시 앞으로 이동
}
int main()
{
	char c;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf(" %c", &c), op[i] = c;
    
	for (int i = 9; i >= 0; i--)//최대값 찾기
	{
		tmp[0] = i;
		check[i] = true;
		if (f(1, 1, 0))	break; //찾으면 종료
		for (int i = 0; i < 10; i++)check[i] = 0;
	}
	for (int i = 0; i <= n; i++)a[i] = tmp[i] + '0'; //문자열 옮기기
    
	for (int i = 0; i < 10; i++)//최소값 찾기
	{
		tmp[0] = i;
		check[i] = true;
		if (f(1, 0, 0)) break;//찾으면 종료
		for (int i = 0; i < 10; i++)check[i] = 0;
	}
	for (int i = 0; i <= n; i++)b[i] = tmp[i] + '0'; //최소값 문자열 옮기기
	printf("%s\n", a);//최대값출력
	printf("%s\n", b);//최소값출력
	return 0;
}

hwooc03 5년 전 2

반례 있습니다~

< < < > <

hwooc03 5년 전 0

답

678945

012435

gdlife 5년 전 0

와 감사합니다!

숫자 찾고 break하면서 check배열이 초기화가 안됬었네요

덕분에 풀었습니다!!

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

문제

문제

출처

ICPC

예제는 맞는데 왜틀렸는지 모르겠습니다

gdlife 5년 전 0

hwooc03 5년 전 2

hwooc03 5년 전 0

gdlife 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말