글 읽기 - [C] 반례를 구합니다

jaehoo1 4년 전 0

DFS 재귀로 풀었는데 반례가 딱히 떠오르지 않습니다...

char 테이블에 입력을 저장하고,

recur()를 실행해 테이블 전체를 돌아보고, 최대/최소값을 구합니다

recur :

int temp = 현재 방문한 숫자 - '0'(char형으로 입력받음)

temp의 값이 0~9일 경우(현재 방문한 위치에 있는 수가 정수일 경우)

cal에 저장된 연산자에 따라 pre변수에 연산을 진행합니다.

그렇지 않다면(현재 방문한 위치에 있는 수가 연산자일 경우)

cal에 현재 위치의 연산자를 넣습니다

마지막으로, 현재 위치가 마지막이라면 대소비교를 통해 max, min값을 저장하고

그렇지 않다면 재귀를 진행합니다

# include <stdio.h>

char arr[5][5];
int N, max, min=9999;
void recur(int pre, char cal, const int x, const int y)
{
	int temp=arr[x][y]-'0';
	if(temp>=0&&temp<=9)
	{
		if(cal=='+')pre+=temp;
		else if(cal=='-')pre-=temp;
		else if(cal=='*')pre*=temp;
		cal=0;
	}
	else	cal=arr[x][y];
	if(x==N-1&&y==N-1)
	{
		if(pre>max)max=pre;
		if(pre<min)min=pre;
		return;
	}
	if(x<N-1)recur(pre, cal, x+1, y);
	if(y<N-1)recur(pre, cal, x, y+1);
}

int main(void)
{
	int i, j;
	scanf("%d", &N);
	for(i=0 ; i<N ; i++)
		for(j=0 ; j<N ; j++)
		{
			getchar();
			scanf("%c", &arr[i][j]);
		}
	recur(arr[0][0]-'0', 0, 0, 0);
	printf("%d %d", max, min);
	return 0;
}

newdeal 4년 전 6

안녕하세요.

반례 첨부해 드립니다.

3
0 - 2
- 2 -
2 - 2
//your answer:0 -4
//correct answer:-4 -4

jaehoo1 4년 전 1

@newdeal

반례 참고해서 고쳐 맞았습니다. 감사합니다!

(max=0이라는 편견을 버려야하겠군요)

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

문제

문제

출처

ICPC

[C] 반례를 구합니다

jaehoo1 4년 전 0

newdeal 4년 전 6

jaehoo1 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말