반응형
https://www.acmicpc.net/problem/3980
🔶 풀이
11명 선수의 포지션 별 능력이 입력된다.
포지션 별로 중복되지 않은 선수 11명을 뽑아서 최대 점수를 구하라.
완전 탐색으로 진행하게 되면 경우의 수는 11! (39,916,800)로 시간 초과가 발생할 수 있다.
때문에 백트래킹을 사용해서 시간 복잡도를 줄여야한다.
위 문제에서 능력치가 0인 경우에는 해당 포지션에 설 수 없다고 했다. 또한, 이미 선발된 선수가 또 다시 선발될 수 없으므로 selected[] 배열로 선발 여부를 처리해준다.
for (int i=0; i<11; i++) {
if (!selected[i] && ability[person][i] > 0) {
selected[i] = true;
getSum(person+1, tmpSum+ability[person][i]);
selected[i] = false;
}
}
선발된 선수 인원을 한 명씩 증가시키면서 재귀함수를 구현하다가 선발 선수 11명을 채웠을 때 최고 능력치합을 구해주면 된다.
<최종코드>
import java.io.*;
import java.util.*;
public class Main {
static boolean[] selected;
static int[][] ability;
static int maxScore;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine()); // 테스트 케이스
while (N-- > 0) {
ability = new int[11][11]; // 포지션 별 능력
selected = new boolean[11]; // 방문 여부
maxScore = 0;
for (int i=0; i<11; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<11; j++) {
ability[i][j] = Integer.parseInt(st.nextToken());
}
}
getSum(0, 0);
System.out.println(maxScore);
}
}
/**
*
* @param person 현재 선택해야하는 선수 idx
* @param tmpSum
*/
public static void getSum(int person, int tmpSum) {
// 11명을 다 뽑았을 경우
if (person == 11) {
maxScore = Math.max(maxScore, tmpSum);
return;
}
for (int i=0; i<11; i++) {
if (!selected[i] && ability[person][i] > 0) {
selected[i] = true;
getSum(person+1, tmpSum+ability[person][i]);
selected[i] = false;
}
}
}
}
반응형
'알고리즘 > 구현 & 그리디 & 브루트포스' 카테고리의 다른 글
[자바로 푸는 백준] 25379번: 피하자 (0) | 2023.05.09 |
---|---|
[백준]JAVA - 8980번: 택배 (0) | 2023.05.06 |
[백준]JAVA - 9576번: 책 나눠주기 (0) | 2023.04.25 |
[백준]JAVA - 19640번: 화장실의 규칙 (1) | 2023.04.21 |
[백준]JAVA - 2146번: 다리 만들기 (0) | 2023.04.06 |