[백준] 20044번 - Project Teams (Java)

https://www.acmicpc.net/problem/20044

20044번: Project Teams

 

 

Project Teams 성공

 

문제

코딩 프로젝트 수업을 가르치는 수찬이는 프로젝트 팀을 가능하면 공정하게 구성하려고 한다. 프로젝트 팀 하나는 두 명의 학생으로 구성되는데, 각 학생들의 코딩 역량은 모두 다르다. 각 학생은 한 팀의 팀원이어야 한다. 공정성을 높이기 위해 수찬이는 팀원 코딩 역량의 합을 최대한 일정하게 유지하려고 한다. 학생들이 코딩 역량이 주어졌을 때 수찬이가 팀을 구성하는데 도움이 되는 프로그램을 작성하라.

문제를 간단하게 하기 위해, 학생 수는 2n이라 가정하자 (n은 양의 정수). 각 학생 si의 코딩 역량은 양의 정수 w(si)로 나타내면 한 i번째 팀 Gi의 코딩 역량은 w(Gi) = ∑s∈Giw(s)로 나타낼 수 있다. 작성할 프로그램 목적은 Sm = min{w(Gi) | 1 ≤ i ≤ n}이 최대화되도록 n개의 팀 G1, G2, …, Gn 을 구성하고 이때 Sm을 출력하는 것이다.

예를 들어, 학생들의 코딩 역량이 {1, 7, 5, 8}로 주어졌다면 (8, 1), (7, 5)로 2개의 조를 짤 수 있으며 프로그램은 9를 출력해야 한다.

 

입력

입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 분리되어 주어진다 (1 ≤ w(si) ≤ 100,000). 학생들의 코딩 역량은 모두 다르다. 즉, i ≠ j이면 w(si) ≠ w(sj)이다.

 

출력

출력은 표준출력을 사용한다. 표준출력 한 행에 Sm을 출력한다.

 

예제 입력 1

2
1 7 5 8

 

예제 출력 1

9

 

 

예제 입력 2

3
1 7 3 5 9 2

 

예제 출력 2

8

 

 

나의 코드

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		
		int[] w = new int[2*n];
		int[] s = new int[n];
		int min = Integer.MAX_VALUE;

		for(int i=0; i<2*n; i++) {
			w[i] = scan.nextInt();
		}

		scan.close();

		Arrays.sort(w);
		
		for(int i=0; i<n; i++) {
			s[i] = w[i] + w[2*n-1-i];
			if(min > s[i]) {
				min = s[i];
			}
		}
		
		System.out.println(min);
		
	}

}

 

※ 체크

1. 팀 수는 n개

2. 학생은 총 2n명

3. 각 팀의 코딩 역량 합이 균등

 

2n명의 코딩 실력으로 오름차순 정렬한 후 양 끝에서 한 명씩 뽑아 팀을 꾸리게 한다.

ex) (맨 앞, 맨 뒤), (맨 앞에서 두 번째, 맨 뒤에서 두 번째) ..... (2n/2 번째, 2n/2+1 번째)

 

그리고 각 팀의 코딩 역량 중에서 최솟값을 찾으면 된다.