글 읽기 - 벡터대신 배열사용했는데 어디가잘못됬나요??

jow1025 4년 전 0

벡터와 lower_bound 함수를 이용해보고 배열로 구현해봤는데 오답이뜨네요..

어디에서 문제가발생하는지 모르겠습니다.

#include<iostream>
#include<algorithm>
using namespace std;
int arr[1000001];
int main()
{
	int n;
	cin >> n;
	arr[0] = 0;
	int num;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> num;
		if (arr[i - 1] < num)
		{
			arr[i] = num;
			cnt++;
		}
		else
		{
			*lower_bound(arr, arr + n, num) = num;
		}
	}
	cout << cnt << endl;
}

herdson 4년 전 0

arr + n 을 최대 범위로 지정하면 배열에 대입되지 않은 쓰레기값도 비교하게 됩니다.

jow1025 4년 전 0

배열을 전역배열로 선언해서 0값을 가지는데 문제에서 최솟값이 1이라 상관없지않나요??

herdson 4년 전 0

그렇네요 이 소스의 또 다른 문제점은 배열의 진행 인덱스를 저장하지 않고 for 루프를 계속 돌린다는 것입니다.

질문자님의 소스를 가지고 수열 1 2 7 5 4 의 경우를 시뮬레이션 한다고 하면

0 1 0 0 0 0

0 1 2 0 0 0

0 1 2 7 0 0

0 1 2 5 0 0

0 1 2 5 0 4

이렇게 되서 cnt가 3이 아닌 4가 나오겠네요

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

문제

문제

출처

ICPC

벡터대신 배열사용했는데 어디가잘못됬나요??

jow1025 4년 전 0

herdson 4년 전 0

jow1025 4년 전 0

herdson 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말