안정적인 결혼
골드 II의견: 0
\(N\)명의 남자와 \(N\)명의 여자가 있다. 각 사람은 이성 전원에 대한 선호 순위를 가지고 있다.
남자와 여자를 일대일로 모두 짝지어 결혼시키려 한다. 어떤 짝짓기에서, 서로 다른 짝에 속한 남자 \(m\)과 여자 \(w\)가 있어 \(m\)은 자신의 현재 배우자보다 \(w\)를 더 선호하고, 동시에 \(w\)도 자신의 현재 배우자보다 \(m\)을 더 선호한다면, 쌍 \((m, w)\)를 불안정 쌍이라 한다.
불안정 쌍이 하나도 존재하지 않는 짝짓기를 안정적인 결혼(stable matching) 이라 한다. 항상 하나 이상의 안정적인 결혼이 존재함이 알려져 있다. 임의의 안정적인 결혼 하나를 출력하여라.
\(1 \le N \le 500\). 각 선호 순위는 \(1 \dots N\)의 순열이다.
첫째 줄에 정수 \(N\)이 주어진다.
다음 \(N\)개의 줄 중 \(i\)번째 줄에는 \(i\)번 남자의 선호 순위가 주어진다. \(N\)개의 정수가 공백으로 구분되어 주어지며, 이는 \(1\)부터 \(N\)까지 여자 번호의 순열로, 앞에 나올수록 더 선호하는 여자이다.
그 다음 \(N\)개의 줄 중 \(j\)번째 줄에는 \(j\)번 여자의 선호 순위가 같은 형식으로 (남자 번호의 순열로) 주어진다.
\(N\)개의 정수를 출력한다. \(i\)번째 정수는 \(i\)번 남자와 짝지어진 여자의 번호이다. 출력한 짝짓기가 완전한 일대일 대응이면서 안정적이기만 하면 정답으로 인정한다.
1
1
1
1
남자도 여자도 한 명뿐이므로 \(1\)번 남자는 \(1\)번 여자와 결혼할 수밖에 없다.
3
1 2 3
2 3 1
3 1 2
2 3 1
3 1 2
1 2 3
1 2 3
각 남자가 1순위 여자와 맺어져도 불안정 쌍이 생기지 않는 안정적인 결혼이 존재한다. 짝짓기 \(1\!-\!1\), \(2\!-\!2\), \(3\!-\!3\)이 그 예이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
안정적인 결혼
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
안정적인 결혼