intdc(intleft,intright){if(left==right){// 판때기가 하나 남았을 경우returnfenceHeight[left]*1;}intmid=(right+left)/2;inttoLeft=mid;inttoRight=mid+1;// 왼쪽에 제일 큰 판때기가 있을 경우// 오른쪽에 제일 큰 판때기가 있을 경우intret=max(dc(left,mid),dc(mid+1,right));inth=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));}returnret;}
안녕하세요 FENCE 문제를 분할정복으로 하던 중 문의가 있어 질문드립니다.
위 내용 중의 중간쯤의 주석으로 표시한 toLeft==left 조건문을 제거할 경우
잘못된 영역 fenceHeight[-1] 등을 참조하는 에러를 제거할 수 있을 것은 같은데, 이부분을 지우고 잘못된 참조를 막는 조건문을 추가하게 되면 시간 초과가 발생하게 됩니다.
이부분이 이해가 되지 않습니다. 분할 정복을 하였는데 해당 조건문 하나로 문제가 초과되고 되지 않는 부분이 이해가 되지않습니다.
임정민
안녕하세요 FENCE 문제를 분할정복으로 하던 중 문의가 있어 질문드립니다.
위 내용 중의 중간쯤의 주석으로 표시한 toLeft==left 조건문을 제거할 경우
잘못된 영역 fenceHeight[-1] 등을 참조하는 에러를 제거할 수 있을 것은 같은데, 이부분을 지우고 잘못된 참조를 막는 조건문을 추가하게 되면 시간 초과가 발생하게 됩니다.
이부분이 이해가 되지 않습니다. 분할 정복을 하였는데 해당 조건문 하나로 문제가 초과되고 되지 않는 부분이 이해가 되지않습니다.
개념적인 부분이 잘못잡힌 것 같은데 도움부탁드리겠습니다.
8년 전