글 읽기 - 문제 이해 관련 도움 및 반례 부탁드립니다!!

wlsgur6941 3년 전 0

우선 최댓값 j 와 최솟값 i 의 값을 뺀 길이가 L-1일 때 count를 증가시켰습니다.

일단 제가 생각해둔 반례는

5 1

1 2 3 4 5일 때 count가 5로 나와야하고

4 3

1 2 3 4 이면 1 2 3을 막고 2 3 4를 겹쳐서 막아서 2가 나오는게 정답인가요?

현재 1%에서 오답처리가 나는군요.

혹시 또 다른 반례나 문제 이해와 관련해서 도움을 주실 수 있다면 감사하겠습니다.!!

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;

bool cmp(int a,int b){
	if(a < b)
	return true;
	else
	return false;
}

int main() {
	int n,l; 
	cin >> n >> l;
	int wp[1001];
	
	for(int i=0;i<n;i++)
	cin >> wp[i];
	
	sort(wp,wp + n,cmp);
	
	int i=0,j=0,count=0;
	
	while(j<n){
	  int tmp = 0;
      j=i;  
      while(tmp < l){
		tmp = wp[j]-wp[i]+1;
		tmp>l?j:j++;
	  }
	  j==n?i++:i=j;  
	  count++;
	}
	
	cout << count;
	
	return 0;
}

nahwasa 3년 전 0

5 1

1 2 3 4 5일 때 count가 5로 나와야하고

-> 네 맞습니다.

0.5~1.5

1.5~2.5

2.5~3.5

3.5~4.5

4.5~5.5

이렇게 5개를 붙였다고 보시면 됩니다.

4 3

1 2 3 4 이면 1 2 3을 막고 2 3 4를 겹쳐서 막아서 2가 나오는게 정답인가요?

-> 네넵.

0.5~3.5과

3.5~6.5 혹은 겹쳐서 1.5~4.5를 막았다고 생각해도 됩니다. 둘다 상관없습니다.

wlsgur6941 3년 전 0

일단 코드를 수정해보았습니다.

그럼

5 2

0.5~2.5

2.5~4.5

4.5~6.5 or 3.5~5.5

결과값 3이 최소의 경우의 수인거네요

넣어본 값들은

1 1000

5 1

1 2 3 4 5

4 3

1 2 3 4

문제를 잘못이해하고 있는걸까요 ㅠㅠ 1퍼센트를 넘지를 못하고 있습니다

wlsgur6941 3년 전 6

결국 풀다보니 해결했습니다

반례가 필요하신분들을 위해 적어둘게요

5 1

1 2 3 4 5

answer : 5

4 3

1 2 3 4

answer : 2

5 2

1 2 3 4 5

answer : 3

5 2

1 2 100 101 1000

answer : 3

5 3

1 2 3 4 1000

answer : 3

2 1000

1 1000

answer : 2

cos8475 3년 전 4

위 반례중 오류가 있어서 댓글 답니다

2 1000

1 1000

정답은 2가 아니고 1입니다

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

문제

문제

출처

ICPC

문제 이해 관련 도움 및 반례 부탁드립니다!!

wlsgur6941 3년 전 0

nahwasa 3년 전 0

wlsgur6941 3년 전 0

wlsgur6941 3년 전 6

cos8475 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말