# [Gold V] 네모난 순열 찾기 2 [문제 링크](https://www.acmicpc.net/problem/34232) ## 문제 설명 <p>$N^2$개의 수가 $N$행 $N$열의 표 $A$에 채워져 있다. 표의 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열에 위치한 칸에는 정수 $A_{r,c}$가 적혀 있으며, $r$행 $c$열을 편의상 $(r,c)$로 표현한다. <strong>이때, 표 $A$에 채워진 값은 모두 다르다.</strong></p> <p>표 $A$에서 직사각형 맨 왼쪽 위 칸이 $(r_1,c_1)$이고, 맨 오른쪽 아래 칸이 $(r_2,c_2)$가 되게 직사각형을 선택할 때, $1\leq r_1\leq r\leq r_2\leq N,1\leq c_1\leq c\leq c_2\leq N$ 을 만족하는 $A_{r,c}$는 직사각형 안에 있는 수이다.</p> <p>수 $x$개로 이루어진 배열이 $1$부터 $x$까지의 서로 다른 정수 $x$개로 이루어져 있다면, 순열이다. 예를 들어 $[2,3,1,5,4]$는 순열이지만, $[1,2,2]$와 $[1,3,4]$는 순열이 아니다.</p> <p>직사각형의 네 변이 표의 경계선과 겹치도록 직사각형을 선택할 때, 직사각형 안에 있는 수를 나열한 것이 순열이 되는 경우의 수는 얼마일까?</p> ## 입력 <p>첫째 줄에 표 $A$의 행과 열의 개수 $N$이 주어진다. ($1\leq N\leq 1\, 000$)</p> <p>이후 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $A_{i,1},A_{i,2},\ldots ,A_{i,N}$이 공백으로 구분되어 주어진다. ($1\leq A_{i,j}\leq N^2$)</p> <p>표 $A$에 채워진 값은 서로 다르다.</p> ## 출력 <p>첫째 줄에 경우의 수를 출력한다.</p> ## 풀이 각 숫자의 인덱스를 기록하고, 1부터 순서대로 모든 숫자를 포함하는 범위를 늘려가며 경우의 수를 찾는 문제입니다. ``` c++ #include<bits/stdc++.h> using namespace std; vector<pair<int, int>> idx(1'000'001); int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int a; cin >> a; idx[a] = {i, j}; } } int cnt=0; int left=n, right=0, up=n, down=0; for(int i=1;i<=n*n;i++) { up = min(up, idx[i].first); down = max(down, idx[i].first); left = min(left, idx[i].second); right = max(right, idx[i].second); if((down-up+1)*(right-left+1)==i) cnt++; } cout << cnt; } ```