글 읽기 - 랜선자르기....왜틀릴까요

90pizza 8년 전 0

초보입니다..왜틀린지 설명해주세요 ㅠㅠ

#include<stdio.h>

int main(void)
{
	int i,j,k,n=0;
	int cnt=0;
	int len[10000]={0,};
	int temp=0;
	int onelen=0;

	scanf("%d %d",&k,&n);
	if(k==n && n==1)
	{
		scanf("%d",&onelen);
		printf("%d",onelen);
		return 0;
	}
	for(i=0;i<k;i++)scanf("%d",&len[i]);
	for(i=0;i<k-1;i++)
	{
		for(j=i+1;j<k;j++)
		{
			if(len[i]>=len[j])
			{
				temp=len[i];
				len[i]=len[j];
				len[j]=temp;
			}
		}
	}//정렬
	for(i=len[0];i>0;i--)
	{	
		cnt=0;
		for(j=0;j<k;j++)
		{
			cnt+=(len[j]/i);
		}
		if(cnt>=n)
		{
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}

mic1021 8년 전 0

질문자분께서 하시는 방법은 랜선자르는 길이를 주어진랜선길이중 가장 작은 길이로 했다가 점점 줄여가는 방법입니다.

3 6

을 넣어보면 1이 나옵니다(원래답은 10)

그렇다면 for문의 시작지점을 주어진랜선의 길이중 가장 큰 길이로 고치면 어떻게 될까요?

그렇게 하면 답이 언젠가는 나오겠지만 랜선 갯수가 엄청 많기 때문에 시간초과가 뜰겁니다

그렇기 때문에 랜선의 길이를 찾기 위해서는 이분탐색의 원리를 적용시켜야 합니다.

90pizza 8년 전 0

감사합니다..초보에게 빛이되네요

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

문제

문제

출처

ICPC

랜선자르기....왜틀릴까요

90pizza 8년 전 0

mic1021 8년 전 0

90pizza 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말