[BOJ/C++] 6525 - 동차 수열

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

---

 

 

n*n 행렬에서 각각의 칸들이 서로 다른 행과 열에 속해있도록 n개의 칸을 선택합니다. 이렇게 선택하는 경우의 수는 총 n!개입니다. 

n!개의 경우의 수에 대해서 n개 원소의 총 합이 모두 같은 지를 판단하는 문제였습니다. 

 

규칙이 있을 것 같은데, 고민해봐도 찾지 못하겠더라구요.

그래서 저의 경우에는 랜덤화를 이용하여 해결했습니다. 

무작위로 1만개의 수열을 생성한 뒤, 합이 일정한지를 확인했습니다.

 

 

문제해결을 하면서 랜덤화를 처음 사용하게 됐는데, 주요 함수는 아래와 같습니다.

// 시드값 (time(NULL))에 대한 난수 생성
mt19937 rng((unsigned int)time(NULL));

// 난수 생성기를 기반으로 배열 셔플
suffle(v.begin(),v.end(),rng)

 

 

 

---

 

코드

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define REP(i,x,y) for(int i=x;i<=y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef tuple<int,int,int> ti3;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
/*----------------------*/

const int MX = 1000;
int board[MX+1][MX+1];
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin>>n){
        if(n==0) break;
        rep(i,0,n) rep(j,0,n) cin>>board[i][j];

        ll sum = 0;
        rep(i,0,n) sum+=board[i][i];

        vector<int> p(n);
        iota(all(p), 0);
        
        bool flag = 1;

        mt19937 rng((unsigned int)time(NULL));
        rep(I,0,10'000){
            shuffle(all(p), rng);

            ll cur = 0;
            rep(i,0,n) cur+=board[i][p[i]];

            if(cur!=sum){
                flag=0;
                break;
            }
        }

        cout<<(flag?"homogeneous\n":"not homogeneous\n");
    }
}