문제 1
문제 링크
스타트와 링크
실버 2
백트래킹 완전탐색
사람들을 반으로 나누어 스타트팀과 링크팀으로 나눈다.
능력치 표 S가 있다.
입력
짝수인 축구할 사람 수 N
능력치 표인 S
출력
능력치 차이가 최소로 하는 팀을 만들고 그 팀의 능력치 차이를 출력한다.
풀이
1. 팀의 구성원을 구한다
=> solve 함수 조합구하는 코드를 사용한다. 1~n까지 인덱스가 존재하는 배열 visited가 true이냐 false이냐에따라 팀이 나눠진다.
basecase는 cnt가 n/2일때이다.
basecase if문 안에서 cal 함수로 이동한다.
2. S[i][j]+S[i][j]를 한 값을 더한다.
=> 1번에서 구한 팀을 기준으로 cal함수에서 nC2의 모든 조합을 for문으로 돌린다.
두개의 i와 j가 모두 visited에서 true인 경우 첫번째 팀이므로 S[i][j]+S[j][i]한 값을 더해준다. 마찬가지로 모두 visited에서 false인 경우는 두번째 팀이므로 동일한 과정을 거친다.
3. 차이를 구한다
=>첫번째 팀의 점수합인 first와 두번째팀의 점수합인 sec 중 어느 것이 더큰지 알 수 없으므로 abs함수를 사용하여 절댓값으로 계산한다.
4. 차이가 최소값을 구한다. (min)
=>cal 함수에서 차이값인 ret을 return 해준다. 다시 solve함수에서 min 함수를 사용해서 min을 갱신해준다. 재귀가 끝나고 min을 출력해주면 답!
코드
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
public static int[][] arr;
public static boolean [] visited;
public static int [] choice;
static int N,T,num=0,ans=0,min=Integer.MAX_VALUE;
static boolean flag;
public static void main(String[] args) {
//입력
N=scan.nextInt();
arr= new int[N+1][N+1];
visited=new boolean[N+1];
choice=new int[N/2+1];
for(int i=1;i<N+1;i++) {
for(int j=1;j<N+1;j++) {
arr[i][j]=scan.nextInt();
}
}
solve(0,1);
System.out.print(min);
}
//팀 나누기 (조합)
public static void solve(int cnt,int pos) {
//basecase
if(cnt==N/2) { //팀의 구성원이 다 모집되었음
//최소값 구하기
min=Math.min(min, cal(visited));
return;
}
for(int i=pos;i<N+1;i++) {
if(!visited[i]) {
visited[i]=true;
solve(cnt+1,i+1);
visited[i]=false;
}
}
}
//나눠진 팀에서 점수 차 계산하기
public static int cal(boolean[] visited) {
int first=0;
int sec=0;
//모든 조합으로 검사
for(int i=1;i<N;i++) {
for(int j=i+1;j<N+1;j++) {
if(visited[i]&&visited[j]) { //첫번째 팀인경우
first+=arr[i][j]+arr[j][i];
}
else if(visited[i]==false&&visited[j]==false){//두번째 팀인 경우
sec+=arr[i][j]+arr[j][i];
}
}
}
int ret=Math.abs(first-sec);
return ret;
}
}어려웠던점
for문이랑 재귀를 엄청 많이 사용해서 생각한대로 코드를 짠다면 시간초과가 날것같고 시도라도 해봐야겠다는 생각은 들지만 코드를 다짜고 이방법으로 풀면 안된다는걸 알게되면 완전 시간낭비+좌절할것같아서 손대기가 무서웠다 ㅠㅠ
문제 2
문제 링크
링크와 스타트
실버 1
완전탐색
사람들을 반으로 나누어 스타트팀과 링크팀으로 나눈다.
1번 문제와 달리 반으로 나눈것이아니라 한명이상의 인원으로만 이루어져있으면 팀이 성립된다.
능력치 표 S가 있다.
입력
짝수인 축구할 사람 수 N
능력치 표인 S
출력
능력치 차이가 최소로 하는 팀을 만들고 그 팀의 능력치 차이를 출력한다.
풀이
위의 풀이에서 팀나누기 (solve함수) 부분을 바꾼다.
1:N-1
2:N-2
...
이런식으로 경우의 수에따라 구해야 하므로 인자 M을 추가하고
solve 함수가 호출되는 부분에서 i가 1부터 N/2+1까지 반복되어 호출될수 있도록 한다.
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
public static int[][] arr;
public static boolean [] visited;
public static int [] choice;
static int N,T,num=0,ans=0,min=Integer.MAX_VALUE;
static boolean flag;
public static void main(String[] args) {
//입력
N=scan.nextInt();
arr= new int[N+1][N+1];
visited=new boolean[N+1];
choice=new int[N/2+1];
for(int i=1;i<N+1;i++) {
for(int j=1;j<N+1;j++) {
arr[i][j]=scan.nextInt();
}
}
for(int i=1;i<N;i++) {
solve(0,1,i);
}
System.out.print(min);
}
//팀 나누기 (M:N-M)
public static void solve(int cnt,int pos,int M) {
//basecase
if(cnt==M) { //팀의 구성원이 다 모집되었음
//최소값 구하기
min=Math.min(min, cal(visited));
if(min==0) {
System.out.println(min);
System.exit(0);
}
return;
}
for(int i=pos;i<N+1;i++) {
if(!visited[i]) {
visited[i]=true;
solve(cnt+1,i+1,M);
visited[i]=false;
}
}
}
//나눠진 팀에서 점수 차 계산하기
public static int cal(boolean[] visited) {
int first=0;
int sec=0;
//모든 조합으로 검사
for(int i=1;i<N;i++) {
for(int j=i+1;j<N+1;j++) {
if(visited[i]&&visited[j]) { //첫번째 팀인경우
first+=(arr[i][j]+arr[j][i]);
}
else if(visited[i]==false&&visited[j]==false){//두번째 팀인 경우
sec+=(arr[i][j]+arr[j][i]);
}
}
}
int ret=Math.abs(first-sec);
return ret;
}
}어려웠던점
min값을 101으로 해놔서 엄청 시간낭비했다 ㅠㅠ 스타트와 링크에서는 돌아가는데 링크와 스타트에서는 안되는듯 !! 항상 min은 안전하게 max_value로 초기화하자 ...!
