글 읽기 - 반례좀 찾아주세요.. ㅠㅠ 도저히 못찾겠네요 ㅎㅎ..

rlgur77 3년 전 0

반례좀 찾아주세요... ㅠㅠ

증가하는 수열 (같은값은 안받음)으로 작성했습니다

같은값도 받는거로 작성해도 안되더라구요

sol 배열에는 index로 과거 값들중 최대값을 넣었습니다.

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

int arr[1000+1];
int sol[1000+1]; 

int N;
int main(void)
{
	int i;
	int max;
	int ind;

	scanf("%d",&N);

	for(i=0;i<N;i++)
	{
		scanf("%d",&arr[i]);
	}
	max = 0;
	sol[0] = arr[0];
	for(i=0; i<N; i++)
	{
		ind = max;
		for(;;)
		{	
			if(sol[ind] < arr[i])
			{
				if(ind == max)
				{
					max++;
					sol[max] = arr[i];
				}
				else
				{
					sol[ind+1] = arr[i];
				}
				break;
			}
			if(--ind<0)
				break;
		}
	}
	printf("%d\n",max+1);
	return 0;
}

buttercrab 3년 전 1

이 소스를 보니까 sol의 처음 값을 항상 배열의 처음값으로 쓰는데 이러면 다음과 같은 반례가 생깁니다.

2 1 2

rlgur77 3년 전 0

맞아요 처음에 큰값이 들어오면 갱신이 안되더라구요

sol[0] 말고 sol[1]에 넣어주니까 해결 됐습니다 ㅎㅎ..

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

문제

문제

출처

ICPC

반례좀 찾아주세요.. ㅠㅠ 도저히 못찾겠네요 ㅎㅎ..

rlgur77 3년 전 0

buttercrab 3년 전 1

rlgur77 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말