글 읽기 - 반례를 모르겠습니다.

pgy3870 2년 전 0

보이는 반례는 거의 넣어본거 같은데

어디서 틀린건지 모르겠습니다..

도와주세요ㅠㅠ

#include<iostream>
#include<vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    vector<long long> v;
    long long K = 0, N = 0, sum = 0, result = 0, sumV = 0, LAN = 0;
    bool IsResultFinded = false, last = false;
    cin >> K >> N;
    for (int i = 0; i < K; i++) {
        cin >> LAN;
        sumV += LAN;
        v.push_back(LAN);
    }
    long long S = 1, E = (long long)(sumV / N), C;//S = 왼쪽 끝, E = 오른쪽 끝, C = 중앙값
    while (S <= E) {
        sum = 0;
        C = (long long)((S + E) / 2);
        for (unsigned int i = 0; i < v.size(); i++) {
            sum += (long long)(v[i] / C);
            if (sum > N) { break; }
        }
        if (sum >= N) {
            if (sum == N) { IsResultFinded = true; }//N에 해당하는 값 발견
            if (result < C) { result = C; }
            if (S == C) {
                S += 1; 
                last = true;//왼쪽과 오른쪽이 1차이이므로 마지막 시도
            }
            else { S = C; }
        }
        else {
            if (IsResultFinded || last) { break; }
            E = C;
        }
    }
    cout << result;
    return 0;
}

dldyddlwl 2년 전 1

아래에 있습니다.

    while (S <= E) {
        
        // ... 중략
        
        if (sum >= N) {
            if (sum == N) { IsResultFinded = true; }
            if (result < C) { result = C; }
            if (S == C) {
                S += 1; 
                last = true;
            }
            else { S = C; }
        }
        else {
            if ( /*IsResultFinded ||*/ last) { break; }      // 저기만 지워주시면 정답입니당!!  
            
            
         //  N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 
         // 이때 만들 수 있는 "최대 랜선"의 길이를 구하는 프로그램을 작성하시오.   라고 문제에 되어있습니다.
         // 위에서 sum == N 인 결과를 한번 찾았다고 해서 바로 break를 하면 위험합니다.
            
         // 수평선으로 생각해봅시다.
            
            // startㅡㅡㅡmidㅡㅡㅡend 에서 mid가 sum==N을 만족해서, isResultFinded 변수를 true로 만듭니다!
            // startㅡㅡㅡmidㅡmid2ㅡend에서 그런데, mid2가 sum < N이면, 루프를 탈출해버리는데, 만약에
  // startㅡㅡㅡmid,mid3,mid2ㅡend에서 만약에 mid3가 실제 답이라면, 더 큰 값인 mid3를 보지 못하고 while문을 나가버립니다. 
            
            
            // 제 생각입니다만, 아마 글쓴이님께서는 한번 답을 찾은 후에(IsresultFinded), sum < N인 경우가 나온다면,
            // 왼쪽 부분에서 답을 찾게 되므로, 당연히 최댓값이 아닐테니까 break를 바로 걸어버리신 것 같습니다.
            
            // 위에 예시가 약간 헷갈릴 수도 있을 것 같습니다.
            // 쉽게 말하자면, 한번 답을 찾았고, sum < N인 mid(여기선 변수 C)에 도달하더라도,
            // S와 C 사이에 만족하는 또 다른 C'이 있을 수 있으므로, break를 쓰시면 안됩니다!

pgy3870 2년 전 0

그동안 시험 기간이라 지금봤네요 !

당시에 뭐가 문제인지 답답했었는데 알려주셔서 감사합니다!!

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

문제

문제

출처

ICPC

반례를 모르겠습니다.

pgy3870 2년 전 0

dldyddlwl 2년 전 1

pgy3870 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말