글 읽기 - 11053번 LIS문제입니다. 반례 찾아주실수있나요?

zionia4758 4년 전 0

메모이제이션 적용해서 DP문제 풀어봤습니다.

게시판 반례 써보고 임의로 몇가지 배열 해봤는데도 답이 잘나오는데 제출만 하면 틀렸다고나옵니다...

혹시 반례를 찾아주실수 있나요??

해결됐습니다.

배열이 자동으로 0으로 초기화 안 되는걸 모르고있었네요 ㅋㅋㅋㅋ

다른분들도 같은 실수 안하길 바라며 이 글은 남겨두곘습니다.

#include <stdio.h>

int arr[1000];
int ret[1000];
int n;

int Max(int a, int b)
{
	if (a > b) return a;
	else return b;
}

int Lis(int start)

{
	//메모이제이션
	if (ret[start] != 0)
		return ret[start];

	//메모이제이션 초기화 이전이면 완전탐색
	ret[start] = 1;
	for (int i = 1; i <= n - start; ++i)
		if (arr[start] < arr[start + i])
			ret[start] = Max(ret[start], Lis(start + i) + 1);

	

	return ret[start];


}


int main()
{

	scanf("%d", &n);
	for (int i = 1; i < n+1; ++i)
	{
		scanf("%d", arr + i);
	}
	//완전 탐색을 위해 arr[0]=-1 추가
	arr[0] = -1;


	//arr[0]추가해준것 감안해서 -1
	printf("%d", Lis(0)-1);

}

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

문제

문제

출처

ICPC

11053번 LIS문제입니다. 반례 찾아주실수있나요?

zionia4758 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말