글 읽기 - 질문 드립니다 !

hhyc2 4년 전 0

정답 소스와 틀린 소스가 조건문 한줄 차이인데 왜 틀리게 되는지 알수 있을까요? ㅠㅠ

#include<stdio.h>
#pragma warning(disable:4996)
int arr[100001];
int N;
int M;
int value = 1e9;
void Search(int min, int max)
{
	if (min > max)
		return;
	int flag = 0;
	int mid = (min + max) / 2;
	int sum = 0;
	int cnt = 1;
	for (int i = 0; i < N; i++)
	{
		if (arr[i] > mid)
		{
			flag = 1;
			break;
		}
		sum = sum + arr[i];
		if (sum > mid)
		{
			sum = arr[i];
			cnt++;
		}
	}
	if (cnt > M || flag==1)
		Search(mid + 1, max);
	else if (cnt <= M)
	{
		if (mid < value)
			value = mid;
		Search(min, mid - 1);
	}	
}
int main()
{
	scanf("%d %d", &N, &M);
	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
		sum = sum + arr[i];
	}
	Search(1, sum);
	printf("%d", value);
}
////// 이 소스가 정답 소스이고 아랫부분이 틀린답입니다
#include<stdio.h>
#pragma warning(disable:4996)
int arr[100001];
int N;
int M;
int value = 1e9;
void Search(int min, int max)
{
	if (min > max)
		return;
	int flag = 0;
	int mid = (min + max) / 2;
	int sum = 0;
	int cnt = 1;
	for (int i = 0; i < N; i++)
	{
		if (arr[i] > mid)
		{
			flag = 1;
			break;
		}
		sum = sum + arr[i];
		if (sum > mid)
		{
			sum = arr[i];
			cnt++;
		}
	}
	if (cnt > M || flag==1)
		Search(mid + 1, max);
	else if (cnt <= M)
	{
		if (cnt == M) // 이 부분이 삭제되니까 정답이 나오는데 이유를 알 수 있을까요 ? 
		{
			if (mid < value)
				value = mid;
		}
		Search(min, mid - 1);
	}
		
}
int main()
{
	scanf("%d %d", &N, &M);
	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
		sum = sum + arr[i];
	}
	Search(1, sum);
	printf("%d", value);
}

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

문제

문제

출처

ICPC

질문 드립니다 !

hhyc2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말