bluefire   4년 전

안녕하세요 정원 문제에서 질문이 있어서 왔습니다.


직사각형 내부에 있는 장미의 개수가 k개가 되도록 직사각형을 2개 선택해야 하는데,


두 직사각형은 서로 겹치는 영역이 없어야 하고, 두 직사각형 둘레의 합이 최소가 되게 2 직사각형을 선택해야 합니다.


제가 생각하는 솔루션은 장미 i와 장미 j를 선택을 해서 장미 i와 장미 j가 있는 위치를 덮는 직사각형을 그렸을 때


영역내부에 있는 장미가 k개가 된다면  해당 직사각형은 유효한 직사각형이라고 생각을 했고 가장 최적이라 생각을 해서


최대 n^2 개의 직사각형만을 그립니다.


그렇다면 한 직사각형의 왼쪽부분에 위치한 직사각형중에서 최소의 둘레를 구하고 마찬가지로 오른쪽 위쪽 아래쪽 이렇게 선택을 합니다.


그렇게 해서 최소의 둘레 합을 구하려고 하는데 틀리네요 왜 틀릴까요?? ㅠㅠ

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