글 읽기 - 랜선 자르기 문제 어디가 틀렸는지 잘 모르겠습니다..

donghoon0709 3년 전 0

이진탐색 구현이 잘못된 것인지 잘 모르겠습니다..

반례가 있다면 알려주시면 감사하겠습니다.

#include<stdio.h>

int lan[10010];

int main() {
	int k, n;	
	scanf("%d %d", &k, &n);
	
	int max_length = 0;
	
	for(int i = 0; i < k; ++i) {
		scanf("%d", &lan[i]);	
		max_length = (max_length < lan[i]) ? lan[i] : max_length;
	}
	
	int low = 1, high = max_length;
	int res_length = 0;
	
	while(low <= high) {
		int cur_length = high + (low - high) / 2;
		int cut = 0;
		
		for(int i = 0; i < k; ++i) {
			cut += lan[i] / cur_length;
		}
		
		if(cut == n) {
			res_length = (res_length < cur_length) ? cur_length : res_length;
		}
		
		if(cut >= n) {
			low = cur_length + 1;
		}
		
		else {
			high = cur_length - 1;
		}
	}
	
	printf("%d", res_length);
	
	return 0;
}

azberjibiou 3년 전 0

코드가 잘못된 점이 2개 있습니다.

첫번째로 cut==n일 때에만 최대 길이의 후보로 하셨는데 자른 랜선의 개수가 n개 이상일 때도 괜찮다고 문제에서 나와있기 때문에 cut>=n으로 고쳐야 합니다.(27줄)

두번째로 cur_length, low, high를 int형으로 하셨는데 랜선 길이 범위가 정확히 int의 범위에 있기 때문에 32줄에서 오버플로우가 날 가능성이 있습니다. 그리고 24줄에서 cut가 int형 범위를 벗어날 수 있기 때문에 오버플로우가 생길 수 있습니다.

그래서 고쳐야 할 점은

27줄의 cut>=n으로 고치기

low, high, cur_length를 long long으로 고치기

cnt를 long long으로 고치기가 있습니다.

그리고 long long 출력할 때에는 %lld로 바꾸는 거 잊지 마세요~

donghoon0709 3년 전 0

감사합니다..! 고민 많이 하고 있었는데 문제를 더 꼼꼼히 읽어야겠습니다!

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

문제

문제

출처

ICPC

랜선 자르기 문제 어디가 틀렸는지 잘 모르겠습니다..

donghoon0709 3년 전 0

azberjibiou 3년 전 0

donghoon0709 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말