백준 13269 - 쌓기나무

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

힌트

만드는 게 우선이다. 일단 주어진 조건에서 가장 적절한 배치를 만들어라.

해설

위에서 본 view(이하 top_view), 앞으로 본 view(이하 front_view)와 옆에서 본 view(이하 side_view)가 주어질 때 가능한 상태인지 확인하고 실례를 출력하는 문제이다.

 

일단 top_view를 입력 받는다. 다음으로 front_view와 side_view를 받으면서 top_view[i][j]의 상태와 front_view[j], side_view[i]의 상태가 모순인지 확인한다. side_view는 왼쪽에서 본 순서로 주어진다는 것을 유의한다.

 

예를 들어서 설명하면 top_view[i][j]가 0인데 front_view[j]가 1이상 값을 가질 수 없다. 반대도 마찬가지. 이런 경우를 먼저 걸러주도록 한다.

 

side_view의 최댓값과 front_view의 최댓값이 일치한지 확인한다. 어디서 보든 가장 높은 높이는 유일해야 한다. 그런데 최댓값이 일치하지 않으면 모순이므로 -1을 출력한다.

 

그러고 나서 일단 나무를 쌓아보자. ans[i][j] = min(side_view[i], front_view[j])로 나무를 쌓는다. 이 식의 의미는 ans[i][j]를 어떻게 보든 min(side_view[i], front_view[j])보다 클 수는 없다는 뜻이다.

 

설명이 이해되지 않는다면 Pizza Boxes를 풀고 올 것을 권고한다.

 

나무를 쌓으면서 우리가 만든 배치의 view를 기록한다. 그리고 다 쌓았을 때 입력으로 주어진 view와 우리가 만든 view를 대조해서 일치하면 배치를 출력하고 그렇지 않으면 어딘가 모순이 발생했다는 뜻이므로 -1을 출력하면 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int n, m;
int top_view[501][501];
int front_view[501];
int side_view[501];
bool row_see[501];
bool col_see[501];
int ans[500][500];
int front_const[501];
int side_const[501];
int mx, mx2;
 
void solve()
{
  cin >> n >> m;
 
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> top_view[i][j];
      
      if (top_view[i][j])
      {
        row_see[i] = col_see[j] = true;
      }
    }
  }
 
  for (int i = 0; i < m; i++)
  {
    cin >> front_view[i];
    mx = max(mx, front_view[i]);
 
    int x = front_view[i] != 0;
 
    if (x ^ col_see[i])
    {
      cout << -1;
      return;
    }
  }
 
  for (int i = n - 1; i >= 0; i--)
  {
    cin >> side_view[i];
    mx2 = max(mx2, side_view[i]);
 
    int x = side_view[i] != 0;
 
    if (x ^ row_see[i])
    {
      cout << -1;
      return;
    }
  }
 
  if (mx != mx2)
  {
    cout << -1;
    return;
  }
 
  for (int i = 0; i < n; i++)
  {
    int lim = side_view[i];
    for (int j = 0; j < m; j++)
    {
      if (top_view[i][j])
      {
        ans[i][j] = min(lim, front_view[j]);
      }
 
      side_const[i] = max(side_const[i], ans[i][j]);
      front_const[j] = max(front_const[j], ans[i][j]);
    }
  }
 
  for (int i = 0; i < n; i++)
  {
    if (side_const[i] != side_view[i])
    {
      cout << -1;
      return;
    }
  }
 
  for (int i = 0; i < m; i++)
  {
    if (front_view[i] != front_const[i])
    {
      cout << -1;
      return;
    }
  }
 
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cout << ans[i][j] << ' ';
    }
    cout << '\n';
  }
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록