[BOJ] 백준 14578. 영훈이의 색칠공부 (Gold II)

PS 단톡방에서 추천받은 문제.

(이거 왜 골드2..? 꽤나 어려웠다.)

문제는 아래와 같다.

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

14578번: 영훈이의 색칠공부

---

의식의 흐름 및 해설

처음에는 b, r을 놓을 수 있는 경우의 수 nC2로 접근하는데 방법이 잘 생각나지 않았다.

2*2부터 순서대로 도형을 그리면 생각나는 dp식이 있지 않을까 접근해보았는데, 오히려 2*2에서 가능했던 경우의 수가 3*3으로 확장되는 경우가 한 가지도 없었다. (눈치빠른 사람이라면 여기서 무언가 눈치챘을 수도 있다.)

 

좀 더 고민해보다가, 색이 어차피 두 가지뿐이므로 b를 먼저 놓는 경우의 수 n!을 생각해보았다.

그 다음으로 r을 놓아야되는데, 어차피 r은 모든 행/열에 하나씩 존재해야된다.

그리고 r은 b와 함께 같은 행과 같은 열에 하나씩 있어야 한다.

여기까지만으로도 느낌이 왔을 수 있지만, 예시를 추가적으로 또 들어보자.

 

예를 들어 3*3에서 b가 (1,1), (2,3), (3,2)에 있다고 하자. 그럼 r은 (1, a), (2, b), (3, c)에 있어야 되는데, a=2,3, b=1,2, c=1,3이 가능하다.

a가 2가 될 경우, b는 1만 가능하고, c는 3만 가능하다.

반대로 a가 1이 될 경우, b는 2만 가능하고, c는 마찬가지로 3만 가능하다.

4*4에서 b가 (1,1), (2,2), (3,3), (4,4)에 있다고 하자. 그럼 a=2,3,4, b=1,3,4, c=1,2,4, d=1,2,3이 된다.

즉, a~d가 모두 중복되지 않은 특정한 값을 제외하고 모두 허용된다.

여기까지 왔다면 아마 느낌이 올 것이다.

 

그렇다. 바로 교란순열 문제이다!

교란순열 문제 특징들이 관찰이 굉장히 어렵다는 점이다.

게다가 이 문제는 같은 색을 우선 다 놓는다는 발상이 굉장히 어렵다.

플레티넘5~골드1 정도의 문제라 생각한다.

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 1e5+3;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
ll N,d[MAX]={0,0,1,2,9,},fac[MAX]={1,1,2,6,24,};
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>N;
    for(int i=5;i<=N;i++){
        d[i]=(d[i-1]+d[i-2])*(i-1);
        fac[i]=fac[i-1]*i;
        d[i]%=MOD;
        fac[i]%=MOD;
    }
    cout<<d[N]*fac[N]%MOD;
}

---

오랜만에 풀어본 재밌는 문제.

덕분에 교란순열 점화식도 다시 한 번 생각해볼 수 있었던 좋은 문제였다~