sw expert academy 4012번 요리사 자바(java) 풀이
문제정리
- 두 명의 손님에게 음식을 제공하며 N개의 식재료가 있다.
- 식재료를 N/2로 나누어 두 개의 요리를 하려고 한다.
- A음식과 B음식의 맛의 차이가 최소가 되어야 한다.
- 식재료 i,j를 같이 쓰면 시너지 Sij가 발생한다.
- 각 음식의 맛은 음식을 구성하는 식재료들로부터 발생하는 시너지들의 합이다.
- 시너지는 1이상 20000이하의 정수이다. (시너지들의 합은 int 범위)
문제 접근
문제를 보자마자 스타트와 링크 문제가 생각이 났습니다.
이는 역량 테스트 기출인데 거의 같다고 생각했습니다.
조합을 통해 식재료 절반을 선택하여 A음식을 만들면 자동으로 반쪽이 B음식의 식재료가 됩니다.
이렇게 하여 두 시너지 합의 최소값을 구하면 된다고 생각하고 풀이하였습니다.
문제 풀이
- 모든 입력을 받고 초기화를 해줍니다.
- N개중 N/2개를 고르는 모든 조합을 따져줍니다. (visited 배열 이용)
- 하나의 조합을 구할때마다 solve 함수를 호출합니다.
visited의 값을 가지고 팀을 나눕니다. (ArrayList 이용)
선택한 재료 인덱스를 가지고 가능한 모든 순열을 구하여 시너지의 합을 구합니다.
두 팀의 시너지 합의 차를 반환합니다.
- 반환된 시너지 합의 차와 min 값을 비교하여 update합니다.
swea 요리사 자바 코드