[알고리즘][X] 월드컵
2024. 2. 15. 13:01ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/problem/6987
package boj.solution6987;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int[] array;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int[][] countries = new int[6][3];
out: for (int k = 0; k < 4; k++) {
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 6; i++) {
int count = 0;
for (int j = 0; j < 3; j++) {
countries[i][j] = Integer.parseInt(st.nextToken());
count += countries[i][j];
}
if (count != 5) {
sb.append(0).append(" ");
continue out;
}
}
int[][] result = new int[6][6];
if (dfs(0, countries, result)) {
sb.append(1).append(" ");
} else {
sb.append(0).append(" ");
}
}
System.out.println(sb);
}
private static boolean dfs(int i, int[][] countries, int[][] result) {
if (i == 5) {
return true;
}
array = new int[5 - i];
int x = 0;
int win = countries[i][0];
int tie = countries[i][1];
int lose = countries[i][2];
for (int j = 0; j < i; j++) {
int r = result[i][j];
if (r == -1) {
lose -= 1;
} else if (r == 0) {
tie -= 1;
} else {
win -= 1;
}
}
for (int j = 0; j < lose; j++) {
array[x++] = -1;
}
for (int j = 0; j < tie; j++) {
array[x++] = 0;
}
for (int j = 0; j < win; j++) {
array[x++] = 1;
}
do {
int[] temp = Arrays.copyOf(array, array.length);
for (int j = i+1; j < 6; j++) {
result[i][j] = array[j-(i+1)];
result[j][i] = 0 - result[i][j];
}
int winCount = 0;
int tieCount = 0;
int loseCount = 0;
for (int j = 0; j < i + 1; j++) {
if (result[i+1][j] == 1) {
winCount += 1;
} else if (result[i+1][j] == 0) {
tieCount += 1;
} else if (result[i+1][j] == -1) {
loseCount += 1;
}
}
if (!(winCount <= countries[i+1][0] && tieCount <= countries[i+1][1]
&& loseCount <= countries[i+1][2])) {
continue;
}
if(dfs(i+1, countries, result)) {
return true;
}
array = temp;
} while(np());
return false;
}
private static boolean np() {
int i = array.length - 1;
while (i > 0 && array[i-1] >= array[i]) {
i--;
}
if (i == 0) {
return false;
}
int j = array.length - 1;
while (array[i-1] >= array[j]) {
j--;
}
int temp = array[j];
array[j] = array[i-1];
array[i-1] = temp;
Arrays.sort(array, i, array.length);
return true;
}
}
나의 풀이
- if (count !=5)를 하지 않으면 count가 5 아래인 경우에는 괜찮지만 5를 넘어가게 되면 ArrayIndex 에러가 터지게 된다.
- 그리고 next permutation을 하려면 먼저 오름차순으로 정렬이 되어 있어야 한다. 그게 안되었기 때문에 결과가 제대로 나오지 않았다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] 최적 경로 (0) | 2024.02.15 |
---|---|
[알고리즘] 상호의 배틀필드 (0) | 2024.02.15 |
[알고리즘] 빵집 (1) | 2024.02.14 |
[알고리즘][X] Z (1) | 2024.02.14 |
[알고리즘] 쿼드트리 (1) | 2024.02.14 |