글 읽기 - 게시판도 다 봤는데 반례 케이스를 찾기가 정말 어렵네요

kangsy763 4년 전 0

그나마 게시판에서 찾은

1 6 2 4 5 3 7

이 값도 통과하게끔 수정하였는데 또 어떤 반례가 있을까요 ?

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int arr[1000] = { 0 };
int main() {
	int n, temp = 0, cnt = 0;
	int idx = 0;
	vector<int> vv;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &temp);
		if (i == 0) {
			arr[idx++] = temp;
			cnt++;
			continue;
		}
		if (temp > arr[idx-1]) {
			arr[idx++] = temp;
			cnt++;
		}
		else {
			int low = lower_bound(arr, arr + i, temp)-arr;
			if (low == i-1) {
				arr[low] = temp;
			}
		}
	}
	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) {
		printf("%d ",arr[i]);
	}
	return 0;
}

pichulia 4년 전 0

23번째 줄의 lower bound 범위가 정말 arr+i까지일까요?

kangsy763 4년 전 0

@pichulia arr+i 말고 arr+idx 인 것 같아서 하는데 오답이라고 뜨네요.. 여담으로 idx cnt 같은 역할이어서 cnt는 굳이 없어도 되겠네요!

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

문제

문제

출처

ICPC

게시판도 다 봤는데 반례 케이스를 찾기가 정말 어렵네요

kangsy763 4년 전 0

pichulia 4년 전 0

kangsy763 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말