백준 14889 스타트와 링크 (Java,자바)
이번에 풀어본 문제는
백준 14889번 스타트와 링크 입니다.
📕 문제 링크
❗️코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int [][] map;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
StringTokenizer st;
for(int i = 0; i < N; ++i)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; ++j)
{
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int startPoint = (int)Math.pow(2,N/2)-1;
StringBuilder sb;
int tmp_cnt;
for(int i = startPoint; i < 1 << N; ++i)
{
sb = new StringBuilder();
tmp_cnt = 0;
for(int j = 0; j < N; ++j)
{
if((i & (1 << j)) > 0)
{
tmp_cnt++;
sb.append("1");
}
else
{
tmp_cnt--;
sb.append("0");
}
}
if(tmp_cnt == 0) diff(sb.toString());
}
System.out.print(min);
}
static void diff(String comb)
{
boolean [] team = new boolean[N];
for(int i = 0; i < comb.length(); ++i)
{
if(comb.charAt(i) == '1') team[i] = true;
}
int total_s = 0;
int total_l = 0;
for(int i = 0; i < N; ++i)
{
for(int j = i+1; j < N; ++j)
{
if(team[i] && team[j]) total_s += map[i][j] + map[j][i];
else if(!team[i] && !team[j]) total_l += map[i][j] + map[j][i];
}
}
if(total_s == total_l)
{
System.out.print(0);
System.exit(0);
}
min = Math.min(Math.abs(total_s - total_l),min);
}
}
📝 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int [][] map;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
StringTokenizer st;
for(int i = 0; i < N; ++i)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; ++j)
{
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int startPoint = (int)Math.pow(2,N/2)-1;
StringBuilder sb;
int tmp_cnt;
for(int i = startPoint; i < 1 << N; ++i)
{
sb = new StringBuilder();
tmp_cnt = 0;
for(int j = 0; j < N; ++j)
{
if((i & (1 << j)) > 0)
{
tmp_cnt++;
sb.append("1");
}
else
{
tmp_cnt--;
sb.append("0");
}
}
if(tmp_cnt == 0) diff(sb.toString());
}
System.out.print(min);
}
static void diff(String comb)
{
boolean [] team = new boolean[N];
for(int i = 0; i < comb.length(); ++i)
{
if(comb.charAt(i) == '1') team[i] = true;
}
int total_s = 0;
int total_l = 0;
for(int i = 0; i < N; ++i)
{
for(int j = i+1; j < N; ++j)
{
if(team[i] && team[j]) total_s += map[i][j] + map[j][i];
else if(!team[i] && !team[j]) total_l += map[i][j] + map[j][i];
}
}
if(total_s == total_l)
{
System.out.print(0);
System.exit(0);
}
min = Math.min(Math.abs(total_s - total_l),min);
}
}
📝 풀이
두 팀을 나누어 각 팀의 능력치 차이가 가장 작을 경우의 수를 구하는 문제입니다. 우선 팀을 반으로 나누어주고, 생성된 조합으로 능력치 값을 누적하여 둘의 차이를 구해줍니다. 두 팀의 능력치가 같아질 경우 최솟값인 0을 구할 수 있으므로, 0을 출력한 후 프로그램을 종료해줄 수 있습니다.
📜 후기
비트마스킹도 잘 활용하고 싶어서 조금은 억지로 써봤는데, 아직 조금 헷갈리고 익숙하지 않은 것 같아요ㅠ 어렵지는 않았던 문제입니다!
Author And Source
이 문제에 관하여(백준 14889 스타트와 링크 (Java,자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jh5253/백준-14889-스타트와-링크-Java자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)