[アルゴリズム]伯俊-開始とリンク
38128 ワード
メモリオーバーフロー
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class baekjoon_14889 {
static int[][] arr;
static int N;
static int arrSum;
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
arr = new int[N+1][N+1];
for (int i = 1; i <N+1; i++) {
String[] inputs = br.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
arr[i][j+1] = Integer.parseInt(inputs[j]);
}
}
arrSum = 0;
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
arrSum += arr[i][j];
}
}
solve(1, "", "");
System.out.println(ans);
}
private static void solve(int curPerson, String startTeam, String linkTeam) {
if (startTeam.length() == N/2 || linkTeam.length() == N/2) {
if (linkTeam.length() == N/2) { // 만약 링크팀이 다 찼다면 나머지는 자동 스타트팀으로 채워준다.
for (int i = curPerson; i <= N; i++) {
startTeam += Integer.toString(i);
}
} else if (startTeam.length() == N/2) {
for (int i = curPerson; i <= N; i++) {
linkTeam += Integer.toString(i);
}
}
int startSum = 0;
int linkSum = 0;
for (int i = 0; i < startTeam.length(); i++) {
for (int j = 0; j < startTeam.length(); j++) {
startSum += arr[Character.getNumericValue(startTeam.charAt(i))][Character.getNumericValue(startTeam.charAt(j))];
}
}
for (int i = 0; i < linkTeam.length(); i++) {
for (int j = 0; j < linkTeam.length(); j++) {
linkSum += arr[Character.getNumericValue(linkTeam.charAt(i))][Character.getNumericValue(linkTeam.charAt(j))];
}
}
ans = Math.min(ans, Math.abs(startSum - linkSum));
return;
}
//curPerson이 스타트 팀에 들어가는 경우
solve(curPerson + 1, startTeam + Integer.toString(curPerson), linkTeam);
//curPerson이 링크 팀에 들어가는 경우
solve(curPerson + 1, startTeam, linkTeam + Integer.toString(curPerson));
}
}
コアロジックは最終的に組み合わせられたようだが、メモリが過剰で通過できなかった.合格した他の人を解く
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
//https://bcp0109.tistory.com/30
public class baekjoon_14889_2 {
static int stoi(String s) { return Integer.parseInt(s); }
static int n;
static boolean[] visited;
static int[][] arr;
static int min = 987654321;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = stoi(br.readLine());
visited = new boolean[n+1];
arr = new int[n+1][n+1];
for(int i=1; i<n+1; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<n+1; j++) {
arr[i][j] = stoi(st.nextToken());
}
}
comb(1, 0);
System.out.println(min);
}
// 모든 팀의 조합 구하기
static void comb(int start, int depth) {
if(depth == n/2) {
min = Math.min(min, getAbilityDifference());
return;
}
for(int i=start; i<n+1; i++) {
if(visited[i] != true) {
visited[i] = true;
comb(i+1, depth+1);
visited[i] = false;
}
}
}
// 팀의 능력치 차이를 구하기
static int getAbilityDifference() {
int sumStart = 0;
int sumLink = 0;
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
// true 면 스타트팀
if(visited[i] && visited[j])
sumStart += arr[i][j];
// false 면 링크팀
if(visited[i] != true && visited[j] != true)
sumLink += arr[i][j];
}
}
return Math.abs(sumStart - sumLink);
}
}
プールコメントブログReference
この問題について([アルゴリズム]伯俊-開始とリンク), 我々は、より多くの情報をここで見つけました https://velog.io/@injoon2019/알고리즘-백준-스타트와-링크テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol