글 읽기 - 두개의 코드의 차이를 모르겠습니다.

hejh6408 5년 전 0

아래의 36번째 줄의 if 문을 주석처리 시키면 맞다고 나오고 , 주석처리를 하지 않으면 틀리다고 나옵니다. 문제에서 반드시 M 개의 휴게소를 지어야 한다고 하였는데 틀린 이유를 모르겠습니다.

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;


int main(void) {
	ios_base::sync_with_stdio(false);
	int N, M, L;
	cin >> N >> M >> L;
    vector<int> pos = {0 , L};
	for (int i = 1; i <= N; i++){
        int t;
        cin >> t;
        pos.push_back(t);
    }

	sort(pos.begin(), pos.end());

	int l = 0, r = L;
	int ans = L;
	N++;
	while (l <= r) {
		int mid = (l + r) / 2;
		int count = 0;

		for (int i = 1; i < pos.size(); i++)
			count += (pos[i] - pos[i - 1] - 1) / mid;


		if (count > M) {
			l = mid + 1;
		}
		else {
            // if(count == M)
      	        ans = min(ans, mid);
			r = mid - 1;
		}
	}
	cout << ans;
	return 0; 
}

kangsw8940 4년 전 4

구하려고 하는 값이 휴게소들 사이의 거리의 최대값 중 최소값이고,

count가 M보다 작은 경우에도 역시 남는 휴게소들(count-M개)은 거리가 최대가 아닌 다른 곳에 아무렇게나 넣어도 최대값 mid는 유지가 될 수 있어서,

꼭 count==M인 경우에만 ans를 넣으면 틀린 답이 나올 수 있는 것 같아요.

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

문제

문제

출처

ICPC

두개의 코드의 차이를 모르겠습니다.

hejh6408 5년 전 0

kangsw8940 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말