글 읽기 - 게시판 테스트케이스 다 돌려보았습니다... 반례 부탁드립니다...

surung9898 5년 전 1

6
10 20 10 30 20 50
4

4
8 10 9 20
3

5
8 10 20 9 20
3

5
10 20 9 10 20
3

5
10 20 8 9 20
3

12
10 20 9 10 20 30 50 40 41 42 37 60
8

1
1
1

2
2 1
1

5
5 4 3 2 1
1

4
1 2 4 3
3

4
1 4 2 3
3

7
8 6 9 1 4 6 7
4

10
4 3 7 4 7 2 5 2 10 7
4

8
2 6 9 5 6 3 8 8
4

6
6 9 4 5 3 7
3

6
5 2 4 8 7 2
3

4
2 2 1 3
2

2
1 1
1

4
10 10 10 10
1

5
1 1 2 1 1
2

10
1 5 10 3 13 18 19 15 16 17
7

3
2 1 2
2

3
1 2 1
2

5
1 2 3 2 3
3

10
1 5 10 3 13 18 19 15 16 17
7

8
1 5 10 3 13 18 15 16
6 //수정

20
2 54 77 21 14 32 68 47 22 10 6 85 77 85 111 140 25 43 31 11
8

8
2 21 32 47 77 85 111 140
8

7
1 2 5 7 3 2 8
5

8
10 20 30 5 10 20 30 40
5

6
10 1 10 30 20 20
3

7
10 40 15 20 30 60 80
6

10
1 6 8 3 4 10 1 2 3 4
4

7
10 100 120 20 30 40 50
5

6
10 20 30 40 10 30
4

9
10 50 60 70 11 12 13 14 15
6

게시판 3페이지 분량 테케 전부 돌려보았고 추가로 몇 개 더 만들어서 돌려보았습니다...

이진 탐색트리로 풀어보려고 했는데 만용이었던 것 같습니다.. 그냥 O(N^2)으로 풀었다면 이런 일도 없었을 텐데...

어디가 잘못 되었는지 가르쳐주시면 정말 좋겠지만 코드가 완전 유사코드라 해석 자체가 난해할 것 같습니다... 테케 돌리고 틀리면 고치고 해서...

제발 반례 부탁드리겠습니다 흑흑...

#include <stdio.h>
#include <stdlib.h>

typedef struct node* link; //binary search tree
typedef struct node
{
	int num;
	int cnt;
	int update;
	link le;
	link ri;
} node;

int max = 1; //최종 출력 대상

int dfs(link c) //dfs라고는 써놓았지만 오른쪽만 탐색...
{
	int cnt = 0;

	if (c->ri)
		cnt += dfs(c->ri);

	return cnt + 1;
}

link bst(link head, link go)
{
	int cnt = 0;
	link c = NULL, tmp = NULL;

	if (!head)
	{
		go->cnt = 1;
		head = go;
		return head;
	}

	c = head;

	while (1)
	{
		if (c->num == go->num) //현재 노드와 같은 숫자의 경우
		{
			if (c->le) //왼쪽 자식노드가 있으면
			{
				cnt += dfs(c->le) + 1;
				c->update = 1;
			}
			else //왼쪽 자식노드가 없으면
				cnt++;

			if (c->cnt < cnt)
			{
				c->cnt = cnt;
				go->cnt = cnt;
			}

			break;
		}
		else if (c->num > go->num) //현재 노드보다 작은 경우
		{
			c->update = 0; //자식 노드 삽입으로 인해, 나중에 부모 노드의 c->cnt의 업데이트가 필요함

			if (!c->le) //왼쪽 자식노드가 없으면
			{
				go->cnt = cnt + 1;
				c->le = go;
				break;
			}
			else //왼쪽 자식노드가 있으면
				c = c->le;
		}
		else //현재 노드보다 큰 경우
		{
			if (c->ri) //오른쪽 자식노드가 있으면
			{
				if (c->le) //왼쪽 자식노드가 있으면
				{
					if (!c->update)
					{
						cnt += dfs(c->le);

						c->update = 1;
					}
					else
						cnt = c->cnt;
				}
				else //왼쪽 자식노드가 없으면
					cnt++;
				
				c = c->ri;
			}
			else //오른쪽 자식노드가 없으면
			{
				if (c->le && !c->update) //왼쪽 자식노드가 있고 업데이트가 필요한 경우
				{
					cnt += dfs(c->le);
					
					go->cnt = cnt + 1;
					c->update = 1;
				}
				else
					go->cnt = c->cnt + 1;

				c->ri = go;
				break;
			}
		}
	}

	if (go->cnt > max)
		max = go->cnt;

	return head;
}
int main(void)
{
	int i, num, temp;
	link head = NULL, tmp;

	scanf("%d", &num);

	for (i = 0; i<num; i++)
	{
		scanf("%d", &temp);

		tmp = (link)malloc(sizeof(node));

		tmp->num = temp;
		tmp->cnt = 0;
		tmp->update = 0;
		tmp->le = NULL;
		tmp->ri = NULL;

		head = bst(head, tmp);
	}

	printf("%d\n", max);

	return 0;
}

surung9898 5년 전 8

그냥 다르게 풀었습니다...

혹시 이 문제 푸시는 분들은

16
8 6 9 1 4 6 7 4 3 7 4 7 2 5 2 10

가 5니까 참고하세요...

kimjh9434 4년 전 0

쿨럭... 저도 잘 풀었다 생각했는데 바로 틀려서 뭘까 하면서 반례를 넣어보니

을 넣었을 때 1이 안나오고 0이 나오더군요... 초기 MAX값을 0에서 1로 바꾸니 바로 통과됬습니다...

cakeme 4년 전 2

위에 테스트케이스

8
1 5 10 3 13 18 15 16
3

답 6입니다~~

dddsss3ddd 2년 전 1

테스트케이스 몰아서 올려주셔서 감사합니다.

jquath 1년 전 1

테스트 케이스 모음 감사합니다....

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

문제

문제

출처

ICPC

게시판 테스트케이스 다 돌려보았습니다... 반례 부탁드립니다...

surung9898 5년 전 1

surung9898 5년 전 8

kimjh9434 4년 전 0

cakeme 4년 전 2

dddsss3ddd 2년 전 1

jquath 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말