[BOJ] 백준 2477 참외밭 (Swift)

문제

https://www.acmicpc.net/problem/2477

2477번: 참외밭

풀이

생각보다 어려웠던 문제입니다..
단순히 큰 사각형에서 작은 사각형을 빼주면 답이 되는데, 작은 사각형의 넓이를 구하는것이 까다로웠습니다.

예시를 한번 그려서 살펴봅시다.

먼저 큰 사각형은 방향이 1번 등장한 것이 큰 사각형을 이루는 변이 됩니다. 4방향과 2방향이 되겠죠??

그 뒤에 빨간색으로 쓴 (1, 60)과 (3, 20)이 작은 사각형의 넓이가 될 것입니다.

작은 사각형이 될것인지 어떻게 알 수 있을까요...

큰 사각형을 이루는 가장 긴 변과 붙어있지 않은 두 변이 가장 작은사각형이 됩니다.

그렇다면 방향이 1번 등장한 것의 길이의 곱이 큰 사각형의 넓이가 되겠죠?

방향이 몇 번 등장했는지는 Dictionary를 활용하였습니다.

이제 큰 사각형을 이루는 가장 긴 변과 붙어있지 않은 두 변을 구해줘야합니다.

방향이 1번 등장한 것이 아닐 때,
현재 방향과 다다음 번의 방향이 같다면 다음번의 길이가 작은 사각형을 이루는 한 변이 됩니다.
제가 써놓고도 무슨말인지 잘 모르겠네요..

다시 이 이미지를 보시면,

(4, 50), (2, 160), (3, 30), (1, 60), (3, 20), (1, 100) 순서로 진행이됩니다.
앞에 두개는 건너 뛰고..
(3, 30)이 (3, 20)과 같은 방향인지 확인합니다. 3으로 같은 방향이네요.
그렇다면 (1, 60)이 작은 사각형을 이루는 한 변이 됩니다. 왜냐하면 긴 사각형을 그리는 변과 인접하지 않기 때문입니다.

마찬가지로 (1, 60)과 (1, 100)이 같은 방향인지 확인합니다. 1로 같은 방향이네요.
그렇다면 (3, 20)도 작은 사각형을 이루는 한 변입니다.

index == index + 2 의 방향이 같다면 index + 1이 작은 사각형을 이루는 변이라고 작성할 수 있겠네요.
이것을 index로 접근하려다 보니, 배열을 이루는 index를 초과해서 접근하게 될 경우가 있기 때문에 모듈러 연산을 통해 작성해줍시다.

이제 (큰 사각형의 넓이 - 작은 사각형의 넓이) * 참외의 개수 를 출력해주면 됩니다.

소스코드

후기

생각보다 어려웠던 문제였습니다.
직접 그려보고 어떻게 구해줘야할지 생각을 많이했던 문제입니다.