# [Silver V] 네모난 순열 찾기 1 [문제 링크](https://www.acmicpc.net/problem/34231) ## 문제 설명 <p>$N^2$개의 수가 $N$행 $N$열의 표 $A$에 채워져 있다. 표의 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열에 위치한 칸에는 정수 $A_{r,c}$가 적혀 있으며, $r$행 $c$열을 편의상 $(r,c)$로 표현한다.</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 15$)</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>첫째 줄에 경우의 수를 출력한다.</p> ## 풀이 $O(N^6)$으로 직접 사각형 내부의 모든 원소를 집어넣으며 가능한 경우의 수를 확인하였다. ``` c++ #include<bits/stdc++.h> using namespace std; int A[15][15]; 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++) cin >> A[i][j]; int cnt=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int k=i;k<n;k++) { for(int l=j;l<n;l++) { set<int> nums; for(int r=i;r<=k;r++) for(int c=j;c<=l;c++) nums.insert(A[r][c]); if(nums.size() == (k-i+1)*(l-j+1) && *nums.begin()==1 && *(prev(nums.end()))==nums.size()) cnt++; } } } } cout << cnt; } ```