FENCE 문제 시간초과 관련 질문드립니다.

  • 임정민
    임정민
    int dc(int left, int right) {
        if (left == right) { // 판때기가 하나 남았을 경우
            return fenceHeight[left] * 1;
        }
    
        int mid = (right + left) / 2;
        int toLeft = mid;
        int toRight = mid + 1;
    
        // 왼쪽에 제일 큰 판때기가 있을 경우
        // 오른쪽에 제일 큰 판때기가 있을 경우
        int ret = max(dc(left, mid), dc(mid + 1, right));
    
        int h = min(fenceHeight[toLeft], fenceHeight[toRight]);
        ret = max(ret, h * 2);
    
        // 걸쳐서 제일 큰 판때기가 있을 경우
        while (toLeft > left || toRight < right) {
            if (toRight < right && (/*이 조건문이 이해가 되지 않습니다.*/toLeft==left || fenceHeight[toLeft-1] < fenceHeight[toRight+1])) {
                ++toRight;
                h = min(h, fenceHeight[toRight]);
            }
            else {
                --toLeft;
                h = min(h, fenceHeight[toLeft]);
            }
    
            ret = max(ret, h*(toRight - toLeft + 1));
        }
    
        return ret;
    }
    

    안녕하세요 FENCE 문제를 분할정복으로 하던 중 문의가 있어 질문드립니다.

    위 내용 중의 중간쯤의 주석으로 표시한 toLeft==left 조건문을 제거할 경우
    잘못된 영역 fenceHeight[-1] 등을 참조하는 에러를 제거할 수 있을 것은 같은데, 이부분을 지우고 잘못된 참조를 막는 조건문을 추가하게 되면 시간 초과가 발생하게 됩니다.

    이부분이 이해가 되지 않습니다. 분할 정복을 하였는데 해당 조건문 하나로 문제가 초과되고 되지 않는 부분이 이해가 되지않습니다.

    개념적인 부분이 잘못잡힌 것 같은데 도움부탁드리겠습니다.


    8년 전
1개의 댓글이 있습니다.
  • 박선준
    박선준
    1. 조건문이 없다면 toLeft값은 toRight<right이고 fenceHeight[toLeft-1] < fenceHeight[toRight+1]일때 음수로 무한 뚫고 나갑니다.
    2. 조건문이 있다면toLeft==left가 참이면 fenceHeight[toleft-1]은 참조되지 않습니다. left가 0일때 fenceHeight[-1]은 참조되지 않습니다.
    3. 왼쪽 끝에 도달한경우 부터는 무조건 오른쪽을 뽑아야 합니다..

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