[BOJ] 참외밭 2477

 

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

2477번: 참외밭

레벨 - 실버1

분류 - 구현, 기하학

 

 

 

 

코드

#include<iostream>
#include <vector>
using namespace std;


int main() {
	int K;
	int result = 0;
	vector<pair<int, int>> len(6);
	cin >> K;
	for (int i = 0; i < 6; i++) {
		cin >> len[i].first >> len[i].second;
		if (i > 0) result += len[i].second * len[i - 1].second;
	}
	result += len.back().second * len.front().second;
	for (int i = 0; i < 3; i++)len.push_back(len[i]);
	int hole = 0;
	for (int i = 3; i < len.size(); i++) {
		if (len[i].first == len[i - 2].first && len[i - 1].first == len[i - 3].first) {
			hole = len[i - 1].second * len[i - 2].second;
			break;
		}
	}
	cout << ((result - 2*hole) / 3)*K;
	return 0;
}

손코딩

 

풀이

좀 이상하게 푼것 같다.

 

6번 주어지는 길이를 각 각 이전 길이와 곱하면(i번째*i-1번째, 마지막에 0번째 * 5번째) 빈공간을 제외하면 3번씩 더해진다.

왜 이렇게 나오는지는 직접 해보면 알것이다.

 

방향을 본다면 계단식으로 되어있어서 빈 공간이 나올 때 1 3 1 3 이나 2 4 2 4 같이 반복으로 수가 나온다.

 

이에 따라 i와 i-2의 방향, i-1과 i-3의 방향이 같다면 i-1*i-2의 값을 빈공간 이라고 하고 전에 더한 값에서 빈공간*2만큼을 빼주고 3으로 나눈 후 1세제곱 미터당 당근 수를 빼서 답을 제출했다. 

 

 

하지만 이런 6각형? 특성상 가장 긴 가로와 가장 긴 세로의 반대쪽 에 빈공간이 있다. 

즉

위의 네가지 경우 밖에 없다.

 

이에 따라 i번째 변과 i+1번째 변의 곱 크기가 가장 클때 i로 부터 i+3번째 변과 i+4번째 곱이 빈공간이기 때문에

 

큰 변에서 이 값을 구하면 더 쉽게 답을 구할 수 있다 가장 긴 변을 찾을 때는 인덱스에 i%6을 잘 활용해 풀면 된다.