빡구현 하기 싫어서(아닌가? 이것도 빡구현가?) 이렇게 구현해 봤습니다. 음 일단 if문으로 일일이 조건처리하지 않았다는 게 더 정확한 표현이겠군요.
혹시 궁금하셨던 분들은 도움이 되셨으면 좋겠습니다.
핵심 아이디어는 다음과 같습니다.
모든 x들과 y들을 각각 배열에 넣어서 정렬 및 중복 값을 제거해준다. (참고로 x,y의 최대 개수는 직사각형이 50개이고, 모든 x,y값들이 중복되지 않는다고 했을 때 직사각형 당 2개를 갖고 있으니 총 100개가 된다.)
그러면 최대 100 x 100 grid가 나오는 데 각 grid에 대한 너비를 미리 계산하여 배열에 저장한다.
각 직사각형마다 해당 직사각형의 grid 좌표인 grid_x1, grid_y1, grid_y2, grid_y2를 저장해 놓는다. 해당 직사각형의 넓이를 구하고 싶으면 grid_x1 ~ grid_x2-1과 grid_y1 ~ grid_y2-1에 대한 grid 너비를 모두 합하면 된다. 맨 마지막 좌표를 빼는 이유는 (i,j)에 대한 grid의 넓이를 계산할 때 (x[i+1]-x[i]) * (y[i+1]-y[i])를 저장했기 때문. 자세한 건 코드를 보면서 참고.
직사각형 높은 번호부터 영역 넓이를 계산하고 사용한 grid는 visit 처리해준다. 그럼 그 다음 직사각형은 해당 grid를 제외하고 너비를 계산하다.
이런 식으로 계산한 너비를 1) 넓이가 큰 순으로, 2) index가 낮은 순으로 정렬한 후 앞의 K개만큼 출력한다.
아래는 제 코드입니다. 음 이걸 백준 게시판에 공유해도 되는지 모르겠는데 혹시 문제가 된다면 코드 지우겠습니다.
jinsoolve 3년 전 2
이 글에는 문제에 대한 해설이 있으므로 스포를 주의해주세요.
빡구현 하기 싫어서(아닌가? 이것도 빡구현가?) 이렇게 구현해 봤습니다. 음 일단 if문으로 일일이 조건처리하지 않았다는 게 더 정확한 표현이겠군요.
혹시 궁금하셨던 분들은 도움이 되셨으면 좋겠습니다.
핵심 아이디어는 다음과 같습니다.
(참고로 x,y의 최대 개수는 직사각형이 50개이고, 모든 x,y값들이 중복되지 않는다고 했을 때 직사각형 당 2개를 갖고 있으니 총 100개가 된다.)
해당 직사각형의 넓이를 구하고 싶으면 grid_x1 ~ grid_x2-1과 grid_y1 ~ grid_y2-1에 대한 grid 너비를 모두 합하면 된다.
맨 마지막 좌표를 빼는 이유는 (i,j)에 대한 grid의 넓이를 계산할 때 (x[i+1]-x[i]) * (y[i+1]-y[i])를 저장했기 때문. 자세한 건 코드를 보면서 참고.
아래는 제 코드입니다. 음 이걸 백준 게시판에 공유해도 되는지 모르겠는데 혹시 문제가 된다면 코드 지우겠습니다.