BOJ 22977 - 달팽이는 그늘에서 쉬고 싶다

그냥 백준을 돌아다니다 재밌어 보여서 풀게 된 문제인데, 풀고 나서 보니 다른 사람들의 풀이와 다른 것 같아 포스팅해보려고 한다.

 

문제

대충 저렇게 생긴 직교 다각형이 주어질 때, 햇빛에 의해 생기는 그늘의 길이를 구하는 문제이다.

 

풀이

코드를 까보니, 다른 분들의 풀이(이자 정해)는 전체 둘레에서 햇빛이 비치는 부분의 길이를 빼서 구하는 방식인 것 같다.

내 풀이의 발상 난이도는 저 풀이와 비슷하거나 조금 쉽고, 접근 방향이 약간 다르다.

여집합이 아니라 그림자의 길이를 직접 구해보자. 그림을 잘 보면,

이런 식으로 각 변에 의한 그림자 길이는 그 변과 같다는 사실을 직관적으로 관찰할 수 있다.

또한, 광원이 하나이기 때문에 그림자가 겹칠 가능성 또한 없음을 파악할 수 있다.

다각형을 이루는 점이 시계방향으로 주어지기 때문에, 그림자를 만드는 변은 올라가는 변 또는 왼쪽으로 가는 변이다.

따라서, 이러한 변들의 길이를 모두 더한 후 2를 곱한 것이 정답이다.