백준 2477 참외밭

큰 직사각형 - 작은 직사각형 하면 되는 간단한 문제인 줄 알았지만 그렇지 않았다.

(큰 직사각형 - 작은 직사각형) 개념을 가져가되, 작은 직사각형의 너비와 높이를 어떻게 구할지 고민해보아야 했던 문제였다.

큰 직사각형의 너비는 direction이 3 혹은 4인 벡터를 따로 만들어 그 중 가장 큰 너비값으로 받고,
큰 직사각형의 높이는 direction이 1 혹은 2인 벡터를 따로 만들어, 그 중 가장 큰 높이값으로 받는다.
(물론, 굳이 따로 벡터를 둘 필요는 없지만 정렬하려고..?)

이제 문제는 작은 직사각형의 너비와 높이를 어떻게 구하느냐인데, 생각보다는 간단하다.

문제를 살펴보면, 일련의 규칙이 존재하기 때문에, 이를 분석해보자면,
1) i번째 값이 height인데, i-1번째 값과 i+1번째 값의 합이 maxWidth값과 동일할 경우
: i번째 값은 작은 직사각형의 높이값이며,
2) i번째 값이 width인데, i-1번째 값과 i+1번째 값의 합이 maxHeight값과 동일할 경우
: i번째 값은 작은 직사각형의 너비값이다.
라는 규칙을 발견할 수 있었다.

이 때, i번째 값이 height이냐 width이냐를 명시적으로 구분해주는 게 좋은 듯하다.
(그렇지 않았다가 몇 번 틀렸다..)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int N;

vector<int> w;
vector<int> h;
struct coor{
  int dir;
  int len;
};

vector<coor> v;
void input(){
  cin >> N;
  for(int i = 0; i < 6; i++){
    int dir, n;
    cin >> dir >> n;
    if(dir == 1 || dir == 2){
      w.push_back(n);
    }
    else if(dir == 3 || dir == 4){
      h.push_back(n);
    }
    v.push_back({dir, n});
  }
}

void solve(){
  sort(w.begin(), w.end());
  sort(h.begin(), h.end());
  int maxW = w[w.size()-1];
  int maxH = h[h.size()-1];
  int minW, minH;
  for(int i = 0; i < 6; i++){
    if(v[i].dir == 3 || v[i].dir == 4){
      //height를 나타내는데, i-1, i+1번째의 합이 maxWidth와 같아지면
      //작은 직사각형의 height.
      if(v[(i+5)%6].len + v[(i+1)%6].len == maxW){
        minH = v[i].len;
      }
    }
    else if(v[i].dir == 1 || v[i].dir == 2){
      //width를 나타내는데, i-1, i+1번째의 합이 maxHeight와 같아지면
      //작은 직사각형의 width.
      if(v[(i+5)%6].len + v[(i+1)%6].len == maxH){
        minW = v[i].len;
      }
    }
  }
  int area = maxW * maxH - minW * minH;
  cout << area * N;
}

int main(void){
  ios_base::sync_with_stdio(false);   
  cin.tie(0);
  cout.tie(0);
  input();
  solve();
  return 0;
}