글 읽기 - 로직의 어디가 틀린건지 아니면 코드 어디에 실수가 있는건지 모르겠습니다.

julysky 3년 전 1

이분탐색 해서 모든 나무토막의 길이가 특정 길이 이하가 되게 할 수 있으면, 특정 길이 줄이고

될수 없으면 특정 길이를 늘리는 작업을 반복해서

최종적으로 가능한 길이 나오게 했고,

체크 할 때 가장 오른쪽부터 나무를 최대한 길게 길게 잘라내서 가능한 가장 왼쪽에 톱질하게 했습니다...

@_@ 어제 밤에 하도 틀려서 아침에 맑은공기 마시고 다시 짜면 될려나 했는데 사실상 같은 로직 같은 머리로 구현한거라 저는 오류를 못찾겠어요...

#include <stdio.h>
int L, K, C;
int cut[10002];	//자르는 위치
int len[10002];	//인접한 자르는 위치 사이 거리. 


int check(int size)
{
	int i, j;
	int use = C;
	int tmp = 0;
	for (i = K; i >= 0; i--)			//맨 오른쪽부터 왼쪽으로 오면서
	{
		if (len[i] > size) return -1;	//더 자를수 없는 토막이 사이즈보다 크면 -1
		tmp += len[i];
		if (tmp > size)					//나무토막이 사이즈보다 크면
		{
			use--;						//이번 토막 직전에 자르고,
			tmp = len[i];				//tmp값 변경.
		}
		if (use == 0)					//더이상 자를 수 없으면
		{
			if (cut[i] > size) return -1;	//남은 토막의 길이와 사이즈비교.
			else return cut[i];
		}
	}
	return cut[0];		//더 자를수 있으면 가장 왼쪽 자름.
}

int main()
{
	int i;
	scanf("%d %d %d", &L, &K, &C);
	if (K < C) C = K;
	for (i = 0; i < K; i++) scanf("%d", &cut[i]);
	cut[K] = L;
	len[0] = cut[0];
	for (i = 1; i <= K; i++) len[i] = cut[i] - cut[i - 1];
	
	//Binary Search
	int s = 1, e = L;
	int ans1 = L;
	int ans2 = L;
	while (s <= e)
	{
		int m = (s + e) / 2;
		int c = check(m);
		if (c >= 0)
		{
			ans1 = m;
			ans2 = c;
			e = m - 1;
		}
		else s = m + 1;
	}
	printf("%d %d\n", ans1, ans2);
}

kcan1416 3년 전 1

len을 구해주시기 전에 cut을 정렬해주셔야합니다

julysky 3년 전 0

헉,,,당연히 순서대로 들어오는줄.. 진짜 고정관념이 무섭네요.. 감사합니다. 해결됐어요!

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

문제

문제

출처

ICPC

로직의 어디가 틀린건지 아니면 코드 어디에 실수가 있는건지 모르겠습니다.

julysky 3년 전 1

kcan1416 3년 전 1

julysky 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말