rancho974   2년 전

preview

점선이 현재 구하고자 하는 영역이고
초록색으로 되어있는 부분들이 이미 구해진 영역이라고 했을때
- 제 생각에는 일부분만 겹친 영역은 제외하고 
- 점선 영역안에서 모든 부분이 구해져있는 부분 영역들만 중복 계산을 없애는데 쓸려고 합니다.

- 겹친 영역이 있으면 둘 중에 하나를 선택해야합니다.

- 그런데 생각해보니 가장 큰 영역을 선택하고 나머지 더할 수 있는 구해진 부분 영역들을 더하게 만들면
   부분 영역 중 가장 큰 사각형은 1개만 쳤을때는 가장 클수도 있지만 그 사각형을 선택하기 위해 겹쳐지는 다른 사각형들을 포기해야합니다.
    만약 포기하는 다른 사각형들의 총합이 1개만 쳤을때 가장 큰 사각형의 영역보다 넓다면
    가장 큰 사각형을 포기하고 다른 사각형들을 택하는게 결과적으로 유리합니다.
이 방향이 맞을지와 함께
혹시 최적화를 더 진행한다면 어떻게 진행할수 있을까요?

jih7368   2년 전

지금 생각하시는 방향보단  전체적으로 구간합을 쭉 구해둔 다음 구간합들을 더하고 빼는 방식으로 필요한 모양을 만드는 것이 좋습니다.

간접적으로 말씀드리자면 구간합이 포함하는 칸은 직사각형 또는 정사각형인데, 어떻게 더하고 빼서 중간에 있는 직사각형을 만들 수 있을지 생각해보시면 될 것 같습니다.

rancho974   2년 전

고맙습니다 ㅎㅎ dp 알고나면 비슷한 방식인데 알기전까지는 어렵네요

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