[BOJ] 2016.λ―Έν μ£Όμ νκΈ°
by λλΆλ2016λ²: λ―Έν μ£Όμ νκΈ°
ννμ΄λ λ€ λͺ μ μΉκ΅¬μ 5λ 5 λ―Έν μ μ°Έμ¬νκ² λμλ€. λ―Έν μ리μμ κ° μ¬λμ μκ°κ° λλκ³ , κ°μμ μ§μ μ ν μκ°μ΄ λμλλ°, ννμ΄κ° λ€μκ³Ό κ°μ λ°©λ²μ μ μνμκ³ , λͺ¨λ μ΄μ μ°¬μ±
www.acmicpc.net
λ¬Έμ
λ―Έν μ리μμ κ°μμ μ§μ μ νλ λ°©λ²μ λ€μκ³Ό κ°μ΅λλ€.
- ννμ΄κ° 1λ², λλ¨Έμ§ λ¨νμμ΄ 2-5λ², μ¬νμμ΄ 6-10λ²μ λλ€.
- κ°μ μλμ λν μ νΈλ μμλ₯Ό 맀겨μ μλλ€.
μ΄λ, λ λͺ μ΄μμ μλμκ² κ°μ μ νΈλλ₯Ό μ μ©νλ©΄ μ λκ³ , 5λͺ λͺ¨λμ λν μμλ₯Ό λ§€κ²¨μΌ ν©λλ€. - 6λ² μ¬νμλΆν° κ°μ₯ μ’μνλ λ¨νμμκ² νλ¬ν¬μ¦λ₯Ό νλ©°, ν΄μ λ§μΌλ©΄ λ€μ μμμ λ¨νμμκ² νλ¬ν¬μ¦λ₯Ό ν©λλ€.
- λ¨νμμ νμ¬ μ§μ΄ μμΌλ©΄ 무쑰건 νλ¬ν¬μ¦λ₯Ό λ°μΌλ©°,
λ λͺ μ΄μμΈ κ²½μ° λ μ νΈνλ μ¬νμκ³Ό μ§μ΄ λκ³ λλ¨Έμ§ μ¬νμμκ² ν΄μ§λ₯Ό λμ΅λλ€. - ν΄μ§ λ°μ μ¬νμλ€λ§ λ€μ λΌμ΄λμμ μ§μ§κΈ°μ μ°Έμ¬ν©λλ€.
λͺ¨λ νμλ€μ΄ μ§μ μ°Ύμ λκΉμ§ μ΄ κ³Όμ μ λ°λ³΅νλ©° λ§μ§λ§μ μλ‘μ μ§μ΄ μ΅μ’ μ§μ΄ λ©λλ€.
ννμ΄μ μ νΈλλ 6 7 8 9 10 μ¬νμ μμμ λλ€.
ν΄λΉ μ νΈλλ₯Ό μ λΉν λ°κΏ μ μ΄μ μλ μ νΈλ 리μ€νΈλ³΄λ€ λ μ’μνλ μ¬νμκ³Ό μ§μ΄ λ μ μλ€λ©΄ "YES", μλλ©΄ "NO"λ₯Ό μΆλ ₯ν©λλ€.
νμ΄
- μ λ ₯μ λ°μ λ μ νΈλ μ 보μ μΈλ±μ€λ₯Ό κΈ°λ°μΌλ‘ μ μλ₯Ό κΈ°μ¬ν©λλ€. ( 0 ~ 4)
- ννμ΄μ μ νΈλλ₯Ό μμ±ν©λλ€. - μμ΄
- μμ λ°©λ²λλ‘ μ§μ μ ν©λλ€.
- μ΄λ―Έ μ§μ μ§μ ν μ¬νμμ μ§ μ νμ νμ§ μμ΅λλ€.
- λ¨νμμ μ§μ΄ μλ κ²½μ°, νμ¬ νλ¬ν¬μ¦ν μ¬νμκ³Ό μ§μ΄ λ©λλ€.
- λ¨νμμ μ§μ΄ μλ κ²½μ°, μ§κ³Ό νμ¬ μ¬νμμ μ νΈλλ₯Ό λΉκ΅νμ¬, μ νΈλκ° λ λμ μ¬νμκ³Ό μ§μ΄ λ©λλ€. (μΈλ±μ€ κΈ°λ° μ μ νμ©)
νμ΄λ μκ°λ³΄λ€ λ μ¬νν©λλ€. μ€μ μ½λλ₯Ό 보μ¬λ리λλ‘ νκ² μ΅λλ€.
import java.util.Scanner;
public class Main {
static int[] myPreference = {6, 7, 8, 9, 10}; // ννμ μ νΈλ
static int[] outputPreference = new int[5];
static int[] outputScores = new int[5];
static int originPartner = 0;
static int changePartner = 0;
static int cnt = 0;
// μ§ μ νκΈ°
public static void getPartner(int[][] preference, int[][] scores) {
preference[1] = outputPreference;
scores[1] = outputScores;
int[] partners = new int[11]; // ννΈλ μ 보 κΈ°λ‘
int[] findPartner = new int[5]; // μ¬νμμ ννΈλ μ 보 κΈ°λ‘
while (true) {
boolean isContinue = false;
for (int i = 6; i < 11; i++) {
if (partners[i] != 0) continue; // μ΄λ―Έ μ§μ μ§μ ν μ¬νμμ μ§ μ ν X
int idx = findPartner[i - 6]; // μ¬νμμ΄ μνλ λ¨νμ μ°μ μμ (μΈλ±μ€)
findPartner[i - 6] = idx + 1; // μ¬νμμ΄ λ€μ μ§μ μ°Ύμ λ μ¬μ©ν μΈλ±μ€
int wantPartner = preference[i][idx]; // μ¬νμμ΄ μνλ λ¨νμ
if (partners[wantPartner] == 0) { // μμ§ μ§μ΄ μ ν΄μ§μ§ μμ
partners[wantPartner] = i;
partners[i] = wantPartner;
} else {
isContinue = true;
int decidedPartner = partners[wantPartner]; // λ¨νμκ³Ό μ§μΈ μ¬νμ λ²νΈ
// μ νΈλ λΉκ΅
if (scores[wantPartner][decidedPartner - 6] > scores[wantPartner][i - 6]) {
partners[wantPartner] = i;
partners[i] = wantPartner;
partners[decidedPartner] = 0; // κΈ°μ‘΄μ μ§μΈ μ¬νμμ μλ‘ μ§μ ν΄μΌ νλ€.
}
}
}
if (!isContinue) break;
}
if (cnt == 0) {
originPartner = partners[1];
} else {
changePartner = partners[1];
}
}
// ννμ μ νΈλ μμ±
public static void setPreference(int len, int[][] preference, int[][] scores, boolean[] used) {
if (1 < cnt && originPartner > changePartner) {
return;
}
if (len == 5) {
// μ νΈλ κ²°κ³Ό ꡬνκΈ°
getPartner(preference, scores);
cnt++;
return;
}
for (int idx = 0; idx < 5; idx++) {
if (!used[idx]) {
used[idx] = true;
int partner = myPreference[idx];
outputPreference[len] = partner;
outputScores[partner - 6] = len;
setPreference(len + 1, preference, scores, used);
used[idx] = false;
}
}
}
public static String solution(int[][] preferences, int[][] scores) {
boolean[] used = new boolean[5]; // μ νΈλ μ¬μ© κΈ°λ‘
cnt = 0;
// μ νΈλ κ³μ°
setPreference(0, preferences, scores, used);
if (originPartner > changePartner) {
return "YES";
} else {
return "NO";
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int testcase = input.nextInt();
int[][] preferences = new int[11][5];
int[][] scores = new int[11][5]; // μ°μ μμμ λ°λ₯Έ μ μ
for (int tc = 0; tc < testcase; tc++) {
// μ νΈλ μ
λ ₯
for (int i = 2; i < 11; i++) {
for (int j = 0; j < 5; j++) {
int partner = input.nextInt();
preferences[i][j] = partner;
if (partner > 5) partner -= 5;
scores[i][partner - 1] = j;
}
}
System.out.println(solution(preferences, scores));
}
}
}
'Algorithm > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] 2660.νμ₯ λ½κΈ° (Java, BFS) (0) | 2023.01.01 |
---|---|
[BOJ] 2615.μ€λͺ© (Java) (0) | 2022.04.21 |
[BOJ] 1759.μνΈλ§λ€κΈ° (Java) (0) | 2021.06.20 |
[BOJ] 12094.Aμ B (Java) (0) | 2021.06.10 |
[BOJ] 10159.μ μΈ (Java) (0) | 2021.05.02 |
λΈλ‘κ·Έμ μ 보
λλΆλμ Devlog
λλΆλ