CANADATRIP 소스 코드 관련해서 질문이 있습니다.

  • Shiner11
    Shiner11

    안녕하세요
    저는 방학 기간 구종만 님의 알고리즘 문제해결전략 책을 가지고 프로그래밍을 학습 중인 컴퓨터학을 이중전공 중인 대학생입니다.

    다름이 아니라 지난 번에 12장의 <최적화 문제 결정문제로 바꿔 풀기> 장에서 CANADATRIP문제를 풀던 중 궁금증이 생기는 부분이 있는데 제가 스스로 해결을 할 수가 없어서 이렇게 알고스팟 질문과 답변 게시판을 이용하게 되었습니다.

    교재 P.458에 나와있는 소스코드를 보면 최적화와 관련하여 소스코드가 다음과 같이 나와 있습니다.

    int optimize() {
      // 반복문 불변식: !decision(lo) && decision(hi)
      int lo = -1, hi = 8030001;
      while(lo+1 < hi) {
        int mid = (lo + hi) / 2;
        if(decision(mid))
          hi = mid;
        else
          lo = mid;
      }
      return hi;
    }
    

    제가 이 코드를 보고 든 의문점은

    int optimize() {
    
      int lo = 0, hi = 8030000;
      while(lo < hi) {
        int mid = (lo + hi) / 2;
        if(decision(mid))
          hi = mid;
        else
          lo = mid;
      }
      return hi;
    }
    

    이렇게 lo와 hi의 값을 바꿔주고 while문 안의 조건에서 lo에 1을 더하는 것을 없애줌으로써도
    코드를 구할 수 있지 않을까였는데..(돌려보니 시간초과가 뜨더군요...)

    혹시 이러한 현상이 발생하는 원인에 대해 설명 좀 해주시겠어요?
    제 머리로는 도저히 이해를 못하겠습니다... ㅜㅜ


    7년 전
2개의 댓글이 있습니다.
  • Corea
    Corea

    lo가 1이고, hi가 2일 때를 생각해보세요. mid가 1이 되고, 이 때decision(mid)가 false라면 lo가 계속 1이 됩니다.


    7년 전 link
  • Shiner11
    Shiner11

    제가 댓글을 너무 늦게 달았네요 ㅜㅜ 감사합니다~!


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.