[구현] 창고 다각형 - 백준 2304번

최대 1 분 소요

풀이

톱니바퀴 문제와 비슷하게 해결하였다.

문제에서 주의해야 할 것은 예시와 달리 가장 긴 막대가 두개 이상이 있을 경우, 볼록한 부분이 생기지 않는다는 것이다.

⇒ 그래서 나는 전체 면적에서 나머지 부분을 빼는 방법을 차용했다.

이렇게 한다면 제일 긴 것과 두번째로 긴 것의 차만큼의 면적을 빼는 것이기 때문에 제일 긴 것과 두번째로 긴 것이 같다면 그것의 차는 0이므로 면적이 없다!!

정렬 후 전체 면적을 먼저 구하고, 가장 긴 막대의 위치(L)와 길이(H)를 찾는다.
가장 긴 막대의 위치가 맨 왼쪽일 경우 왼쪽으로 더 나아갈 필요가 없고, 맨 오른쪽일 경우 오른쪽으로 더 나아갈 필요가 없기 때문에 조건문을 잘 걸어준다.
첫번째부터 가장 긴 막대가 있는 곳까지 중에서 두번째로 긴 막대를 찾아준다. == 막대 기준 왼쪽에서 가장 긴 막대
높이의 차 x 전체 면적의 왼쪽 끝 위치 를 전체 면적에서 뺀다.
가장 긴 막대가 있는 곳부터 전체 면적 끝까지 중 두번쨰로 긴 막대를 찾아준다. == 막대 기준 오른쪽에서 가장 긴 막대
높이의 차 x 전체 면적의 오른쪽 끝 위치 를 전체 면적에서 뺀다.
두번째 막대들이 양 끝이 아니라면 끝일 때까지 상자 빼기를 반복한다.