[알고리즘] ⚾
2024. 2. 23. 13:11ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/problem/17281
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] order;
static boolean[] visited;
static int N;
static int[][] innings;
static int maxScore;
static int[] nps;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
innings = new int[N+1][10];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= 9; j++) {
innings[i][j] = Integer.parseInt(st.nextToken());
}
}
order = new int[10];
visited = new boolean[10];
order[4] = 1;
maxScore = Integer.MIN_VALUE;
nps = new int[] {2, 3, 4, 5, 6, 7, 8, 9};
do {
game();
} while(np());
// dfs(1);
System.out.println(maxScore);
}
private static void dfs(int depth) {
if (depth == 4) {
dfs(depth+1);
return;
}
if (depth == 10) {
game();
return;
}
for (int i = 2; i <= 9; i++) {
if (!visited[i]) {
visited[i] = true;
order[depth] = i;
dfs(depth+1);
visited[i] = false;
}
}
}
private static boolean np() {
int i = 7;
while (i > 0 && nps[i-1] >= nps[i]) {
--i;
}
if (i == 0) {
return false;
}
int j = 7;
while (nps[i-1] >= nps[j]) {
--j;
}
int temp = nps[i-1];
nps[i-1] = nps[j];
nps[j] = temp;
for (int k = 0; k < (7 - i + 1) / 2 ; k++) {
temp = nps[i+k];
nps[i+k] = nps[7 - k];
nps[7 - k] = temp;
}
return true;
}
private static void game() {
int index = 0;
int base = 0;
int score = 0;
for (int i = 1; i <= N; i++) {
base = 0;
int outcount = 0;
while(outcount < 3) {
int curIndex = index % 9;
// int playerNumber = order[(index % 9) + 1];
int playerNumber = -1;
if (curIndex <= 2) {
playerNumber = nps[curIndex];
} else if (curIndex == 3) {
playerNumber = 1;
} else {
playerNumber = nps[curIndex-1];
}
int heatNumber = innings[i][playerNumber];
switch (heatNumber) {
case 0:
outcount++;
break;
case 1:
base <<= 1;
base += 1;
if ((base & (1 << 3)) != 0) {
score++;
}
break;
case 2:
base <<= 1;
base += 1;
base <<= 1;
for (int j = 0; j < 2; j++) {
if ((base & (1 << 3 + j)) != 0) {
score++;
}
}
break;
case 3:
base <<= 1;
base += 1;
base <<= 2;
for (int j = 0; j < 3; j++) {
if ((base & (1 << 3 + j)) != 0) {
score++;
}
}
break;
case 4:
base <<= 1;
base += 1;
base <<= 3;
for (int j = 0; j < 4; j++) {
if ((base & (1 << 3 + j)) != 0) {
score++;
}
}
break;
}
index++;
}
}
maxScore = Math.max(maxScore, score);
}
}
나의 풀이
- 조합을 구할 때 next permutation을 활용할 수도 있고 재귀를 이용할 수도 있다.
- 현재 주자를 나타낼 때 비트마스킹을 활용하여 간단하게 표현할 수 있다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] 점심 식사시간 (0) | 2024.02.25 |
---|---|
[알고리즘] DP 테이블의 차원에 대한 꿀팁 (0) | 2024.02.24 |
[알고리즘] 게리맨더링 (0) | 2024.02.22 |
[알고리즘][X] 숨바꼭질 3 (0) | 2024.02.20 |
[알고리즘][X] 숨바꼭질 4 (0) | 2024.02.20 |