글 읽기 - 자꾸 틀립니다....ㅠㅠ

pwc99 5년 전 0

전에 두 번이나 질문을 올렸는데 전에는 알고리즘상에 문제가 있었습니다.

그런데 이제는 여러 케이스를 받았던 것도 모두 잘 되는데도 틀렸다고 나옵니다...

어떤 데이터가 틀린걸까요?

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

int binLowerBound(int bound[],int lo,int hi,int x){
  if (lo >= hi)
    return lo;
  int mid = (lo + hi) / 2 ;
  if (bound[mid] > x)
    return binLowerBound(bound,lo, mid-1, x);
  else
    return binLowerBound(bound,mid+1, hi, x);
}

int main(void){
	int n;
	int i,bnd_idx=1;

	int *a;
	int *bound;

	a = (int*)malloc(1000005*4);
	bound = (int*)malloc(1000005*4);

	scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&a[i]);
		}

		bound[0] = a[0];
		for(i=1;i<n;i++){
				if(bound[bnd_idx-1] < a[i] ) {	//bigger than the last bnd_idx, insert to the last.
					bound[bnd_idx] = a[i];
					bnd_idx++;
				} else {
					if(bound[binLowerBound(bound,0,bnd_idx-1,a[i])-1] != a[i]) {
						if(binLowerBound(bound,0,bnd_idx-1,a[i]) == bnd_idx-1){
							bound[bnd_idx-1] = a[i];
						}
						else if(binLowerBound(bound,0,bnd_idx-1,a[i]) == 0 && bnd_idx >= 2 && bound[0] < a[i]){
							bound[1] = a[i];
						}
						else {
							bound[binLowerBound(bound,0,bnd_idx-1,a[i])] = a[i];
						}
					}
				}
			}

	printf("%d",bnd_idx);

	return 0;
}

jh05013 5년 전 1

잘 되는데 틀리는 건 없습니다. 틀리니까 틀리는 겁니다. 이번에도 알고리즘상에 문제가 있을 겁니다.

원하시는 게 데이터 뿐이라면 혼자서도 간단하게 얻어낼 수 있습니다. 확실히 맞는 O(N^2) 함수를 짜고 (11053번 문제), 랜덤 데이터를 만들어서 일치하는 값이 나오는지 검사하면 됩니다.

pwc99 5년 전 0

넵 감사합니다.

다시 봐보겠습니다.

djm03178 5년 전 3

여기 한 번 더 드립니다.

14
7 1 2 3 3 9 5 10 9 10 6 3 8 10 
correct = 7, wrong = 6

13
6 5 1 9 2 6 8 10 3 8 4 7 10 
correct = 6, wrong = 5

14
1 9 2 5 3 3 7 9 6 3 10 7 9 10 
correct = 7, wrong = 6

11
9 1 2 8 9 10 3 5 6 8 6 
correct = 6, wrong = 5

14
1 3 9 4 1 5 9 10 9 7 4 4 8 9 
correct = 7, wrong = 6

13
1 3 10 2 3 3 4 9 10 5 5 6 8 
correct = 7, wrong = 6

14
1 3 8 9 10 4 1 10 10 7 1 10 8 9 
correct = 6, wrong = 5

12
7 1 2 5 2 8 10 3 8 4 6 7 
correct = 6, wrong = 5

14
1 4 4 2 4 3 6 4 7 10 5 7 4 9 
correct = 7, wrong = 6

14
7 1 4 7 1 8 3 10 4 7 5 6 9 5 
correct = 6, wrong = 5

pwc99 5년 전 0

djm03178님 정말 감사합니다...

이전 오류들도 주신 틀린케이스로 찾았어요.

새 케이스들로 다시 디버깅 해보겠습니다.

감사합니다.

pwc99 5년 전 0

해결됐습니다.

정말 감사합니다.

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

문제

문제

출처

ICPC

자꾸 틀립니다....ㅠㅠ

pwc99 5년 전 0

jh05013 5년 전 1

pwc99 5년 전 0

djm03178 5년 전 3

pwc99 5년 전 0

pwc99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말