sw expert academy의 요리사 (4012와 유사함)
15661번: 링크와 스타트
첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100
www.acmicpc.net
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N;
static int[][]S;
static boolean[] visit;
static int answer=Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
N=sc.nextInt();
S=new int[N+1][N+1];
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
S[i][j]=sc.nextInt();
}
}
visit=new boolean[N+1];
for(int i=1;i<=N/2;i++) { //횟수
for(int j=1;j<=N;j++) { //시작 인덱스
visit[j]=true;
solution(j,1,i);
visit[j]=false;
}
}
System.out.println(answer);
}
static void solution(int i, int cnt, int count) {
if(cnt==count) {
//차이 확인
answer=Math.min(answer, count(cnt));
return;
}
for(int j=i+1;j<=N;j++) {
if(!visit[j]) {
visit[j]=true;
solution(j,cnt+1, count);
visit[j]=false;
}
}
}
static int count(int t) { //true의 개수
int f=N-t;
int t_sum=0;
int f_sum=0;
//true 팀
if(t==1) t_sum=0;
else {
for(int i=1;i<=N;i++) {
if(!visit[i]) continue;
for(int j=1;j<=N;j++) {
if(visit[j]) t_sum+=S[i][j];
}
}
}
if(f==1) f_sum=0;
else {
for(int i=1;i<=N;i++) {
if(visit[i]) continue;
for(int j=1;j<=N;j++) {
if(!visit[j]) f_sum+=S[i][j];
}
}
}
return Math.abs(f_sum- t_sum);
}
}
'코테 공부' 카테고리의 다른 글
트리의 부모 찾기(백준 11725번, 자바) (0) | 2023.02.16 |
---|---|
[SWEA] 사칙연산 유효성 검사(1233번, 자바) (0) | 2023.02.15 |
배열돌리기2(백준 16927번, 자바)☆ (0) | 2023.02.15 |
배열 돌리기 1(백준 16926번, 자바) (0) | 2023.02.15 |
[SWEX] 암호문1(1228번, 자바)☆ (0) | 2023.02.14 |