BOJ 2477 참외밭

 

문제 링크 : https://www.acmicpc.net/problem/2477

2477번: 참외밭

 

이 문제 자체 보다 생각해 봐야할 것이 있어서 기록해 둔다.

 

1.  방향에 대한 정보는 필요없다?!

주어진 문제이 도형은 큰 직사각형에서 작은 직사각형을 제거한 형태이다.

둘레의 길이라는 측면에서 보면 큰 직사각형을 형성하는 두 변의 길이의 합이 전체의 절반이 된다.

이 사실을 이용하면 방향에 대한 정보는 필요가 없다.

 

이렇게 해결하는 코드는 다음과 같다.

 

#include<bits/stdc++.h>

using namespace std;

int arr[6];

int main(){
    int ratio; scanf("%d",&ratio);
    
    int s=0;
    for(int i=0;i<6;i++){
        int x; scanf("%d%d",&x,&arr[i]);
        s+=arr[i];
    }
    
    int ans=0;    
    for(int i=0;i<6;i++){
        int j=(i+1)%6;
        if(arr[i]+arr[j]==s/2){
            ans=arr[i]*arr[j];
            int p=(j+2)%6, q=(j+3)%6;
            ans-=arr[p]*arr[q];
            break;
        }
    }
    
    printf("%d\n", ans*ratio);
}

 

i , (i+1)%6 은 이웃하는 두 변의 번호임은 쉽게 이해가 될 것이다.

원하는 지점을 찾았다면 제거해야할 작은 직사각형의 두변은 (i+3)%6 ,(i+4)%6 이 된다.

 

2. 방향 정보를 이용하는 법

방향 정보를 이용하는 방식은 말로 때우자. 

반시계방향으로 움직이면 '동 -> 북 -> 서 -> 남 -> 동 ->...' (1->4->2->3->1->...) 의 방식으로 움직여야 한다.

따라서 동쪽 다음에 남쪽이 나오거나 하는 등의 일이 벌어지면,

그곳은 향(orientation)이 바뀐 곳이니 오목하게 들어간 두 변이다.

 

3. 생각해 볼 것!

방향에 대한 정보가 추가적으로 주어졌음에도 그것을 이용한다해서 더 쉬운 풀이가 되지는 않음을 보았다.

이는 주어진 도형이 비교적 간단한 형태이기 때문이었을까?

만약 십자가 모양등의 더 복잡한 도형일 경우에 변의 길이만으로 문제를 해결할 수 있는가?