[BOJ] 14889번: 스타트와 링크, [SWEA] 4012번: 요리사
문제
SWEA(SW Expert Academy) 4012번- [모의 SW 역량테스트]요리사
백준 14889번-스타트와 링크
14889번: 스타트와 링크
풀이
A, B요리 각각 재료를 반씩 나눠가지기 때문에 A요리 재료를 선택한 후 남은 재료를 B요리에 사용 -> 조합
A요리에 선택된 재료의 정보는 isSelected 배열에 해당 인덱스를 true로 바꿔줌으로써 저장
조합 알고리즘에 기저조건을 재료가 N/2개 선택되었을 때로 정함
기저조건 달성 시, 현재 조합으로 맛을 비교하는 compTasty메소드 실행
현재 조합에서의 맛 차이(compTasty() 결과값)와 기존의 맛 차이 중 최솟값(tasty) 비교
코드
import java.io.*;
import java.util.*;
public class Solution{
static int N;
static int[][] arr; //시너지 배열을 저장하는 변수
static boolean[] isSelected; //a조합에 선택된 재료 idx: true, b조합에 선택된 재료 idx: false
static int tasty; //결과 값(=최소 맛 차이)
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine()); //테스트케이스 수
for(int T=1 ; T<=tc ; T++) {
N = Integer.parseInt(br.readLine()); //재료의 수
arr = new int[N][N];
for(int i =0 ; i < N ; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int j =0 ; j < N ; j++) {
arr[i][j] = Integer.parseInt(st.nextToken()); //시너지 값 저장
}
}
isSelected = new boolean[N];
tasty = Integer.MAX_VALUE;
comb(0,0);
sb.append("#").append(T).append(" ").append(tasty).append("\n");
}
System.out.println(sb.toString());
}
//재료의 조합을 결정하는 메소드
static void comb(int cnt, int start) {
if(cnt == N/2) { //기저조건: 재료가 N/2개 선택되었을 때
tasty = Math.min(tasty, compTasty()); //현재 조합으로의 맛 차이(compTasty()), 기존의 맛차이(tasty) 중 최솟값 선택
return;
}
for(int i = start ; i < N ; i++) {
isSelected[i] = true; //선택된 재료: true
comb(cnt+1, i+1); //다음자리 조합 뽑으러
isSelected[i] = false; //다음 조합에 영향을 주지 않기 위해 다시 초기화
}
}
static int compTasty() {
int[] a = new int[N/2] , b = new int[N/2]; // a, b 요리 재료의 idx를 저장하는 배열
int a_idx = 0, b_idx = 0;
for(int i =0 ; i < N ; i++) {
if(isSelected[i]) a[a_idx++] = i; //조합에서 선택되었다면 a요리
else b[b_idx++] = i; //선택되지 않았다면 b요리
}
int a_ts = 0, b_ts =0; //a, b 요리의 맛
for(int i = 0 ; i < a.length ; i++) {
for(int j = 0 ; j<a.length ; j++) {
a_ts += arr[a[i]][a[j]]; //요리의 각 재료간의 시너지를 더함
b_ts += arr[b[i]][b[j]];
}
}
return Math.abs(a_ts - b_ts);
}
}
Author And Source
이 문제에 관하여([BOJ] 14889번: 스타트와 링크, [SWEA] 4012번: 요리사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-14889번-스타트와-링크-SWEA-4012번-요리사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)