백준 BOJ 2477 - 참외밭

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

2477번: 참외밭

참으로귀찮게생겨먹어서 미루다미루다 푼 문제

한번에 안풀려서 질문창 보다가 느낀건데

이문제 다들 너무 어렵게 생각하고 있는 것 같다.

 

이 문제를 유심히 보면

패인 부분에 있는 60이라는 길이와 인접한 두 변이

평행선을 그리면서,

반시계방향으로 탐색하게 된다면 반드시 남쪽으로 내려가는 변이라는 것을 알 수 있다.

 

똑같이 패인 부분에 있는 길이가 20인 변과

인접한 두변의 탐색방향이 동쪽으로 동일하다는 점을 통해서,

 

어떠한 선이 패인 선, 즉 빼야하는 넓이에 포함되는 선인지의 판별 방법은

배열을 순회하면서 배열의 앞 인덱스와 뒷 인덱스의 방향이 같은 경우가 되겠다.

 

이를 통해 넓이를 뺄때 찾아줘야 하는 두개의 선을 찾았다면

나머지 선들 중에서 큰 부분의 넓이에 해당하는 부분은 그냥 단순히

해당 방향에 대한 입력이 한번밖에 들어오지 않았던 변을 구하면 된다.

 

순회할때 배열의 양 끝에서 순회할 경우, 반대쪽 배열에서 값을 가져와야 한다는것에 주의하자

순회시 배열 인덱스가 0이면,

인접한 두 인덱스는 각각 -1 과 1인데,

이 경우 -1을 5로 바꿔서 배열의 제일 끝 값과 비교해줘야 한다.

 

이를 위한 함수 idx() 를 작성했다.

int idx(int k){
	if(k<0) return k+6;
	return k%6;
}

전체 정답 소스코드는 아래와 같다.

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<pair<int,int>> v;
int cnt[10] = {0};

vector<int> large;
vector<int> small;

int idx(int k){
	if(k<0) return k+6;
	return k%6;
}

int main(){
	int N;
	int a,b;
	
	int large = 1;
	int small = 1;
	
	cin >> N;
	
	for(int i=0; i<6; i++){
		cin >> a >> b;
		v.push_back({a,b});
		cnt[a]++;
	}
	
	for(int i=0; i<6; i++){
		if(v[idx(i-1)].x == v[idx(i+1)].x){
			small *= v[i].y;
		}
		else if(cnt[v[i].x] == 1){
			large *= v[i].y;
		}
	}
	
	cout << (large - small) * N;
	return 0;
}

여러모로 귀찮았던 문제....