글 읽기 - 숫자구슬 질문 드립니다.

ashi3914 6년 전 0

파라매트릭 서치유형을 연습하고자 몇가지 풀어보는 도중에 숫자 구슬을 풀게되었습니다.

이문제를 풀기전에 같은유형인 2110번 공유기설치 과 구간 나누기2 를 풀었습니다.

이문제도 비슷하게 코딩을 하였습니다. 당연히 나와있는 예제는 답이 제대로 나왔습니다.

그러나 제출을하면 오답으로 뜨더군요.. 제 코드 봐주시고 틀린 부분이 있는지 알려주셨으면 좋겠습니다.

아니면 오류가 나는 다른 testcase를 알려주셔도 정말 감사하겠습니다.

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

int n,m;
int group(int c,int *a);
void solve(int c,int *a);

int main(){

	int l,r,c;
	int *arr;
	scanf("%d %d",&n,&m);

	arr=(int*)malloc(sizeof(int)*n);
	for(int i=0;i<n;i++){
		scanf("%d",arr+i);
	}
	l=1,r=100;
	while(l<=r){

		c=(l+r)/2;
		if(group(c,arr)>m){
			l=c+1;
		}
		else{
			r=c-1;
		}
	}
	solve(c,arr);
	free(arr);
	return 0;
}

int group(int c,int *a){

	int sum=0,count=1;
	for(int i=0;i<n;i++){
		sum+=a[i];
		if(sum>c) sum=0,count++;
	}

	return count;
}
void solve(int c,int *a){

	int sum=0,max=0,count=0,coin=0;
	int *num;
	num=(int*)malloc(sizeof(int)*n);
	for(int i=0;i<n;i++){
		sum+=a[i];
		coin++;
		if(sum>c){
			if(sum>max){
				max=sum;
			}
			sum=0;
			num[count]=coin;
			count++;
			coin=0;
		}
	}
	printf("%d\n",max);
	for(int i=0;i<count;i++){
		printf("%d ",num[i]);
	}
	free(num);
}

djm03178 6년 전 0

질문 게시판에 반례들이 있습니다.

ashi3914 6년 전 0

죄송하지만 반례들을 어디서 찾을수 있나요??... 아무리 찾아봐도 안보이네요 ㅠ

djm03178 6년 전 0

www.acmicpc.net/board/view/179... 여기 있는 것들부터 틀리게 나왔습니다.

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

문제

문제

출처

ICPC

숫자구슬 질문 드립니다.

ashi3914 6년 전 0

djm03178 6년 전 0

ashi3914 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말