[백준] 23742번 Player-based Team Distribution 자바

문제

 

23742번: Player-based Team Distribution

 

 

문제 풀이

 

일단, 양수팀은 인원이 많으면 많을 수록 그 배수로 늘어나므로 양수팀끼리 묶는다.

또, 팀은 1명 이상이기만 하면 되므로 음수는 각각 다 1인 팀으로 묶는다.

양수가 많이 큰 수 이면 음수를 데려와서 그 인원수를 곱했을 경우 기존 점수합보다 더 커질수도 있으므로 음수팀에서 음수값이 더 작은 플레이어를 데려와 양수팀과 합쳐서 점수합을 갱신해나간다.

이때, 음수는 -값이 작은 것부터 넘긴다. 왜냐하면 그래야 곱했을 때도 더 작은 값이라 최대값이 나올 수 있기 때문에.

 

처음에 음수배열에서 하나씩 양수배열로 옮기면서 양수배열에 있는 모든 값을 다시 계산해주면서 이중 포문썼는데 시간초과가 떴다. 양수배열의 합 자체는 그대로 유지되면서 곱하는 인원수만 바뀌는 것이기 때문에 굳이 포문을 한 번 더 안써도 된다.

분배법칙? 생각하면 쉽다. 2(a+b+c) = 2a + 2b + 2c 이런 것처럼 양수배열도 총합을 유지하면서 음수배열에서 하나 가져오면 양수합 갱신하고 곱하기만 바로 바꿔주면 값갱신 된다.

 

❗양수 음수 계산할때 부호 조심해야함

❗N의 조건에 맞춰 데이터 타입 long으로 해야함

 

 

소스 코드

 

public class b_23742 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		long[] parr = new long[N]; 	  //양수 넣는 배열
		long[] narr = new long[N]; 	  //음수 넣는 배열
		int pidx = 0, nidx = 0, pCnt;	  //각 배열 인덱스, 양수배열 개수 카운트 변수	
		long ans = 0, nsum = 0, psum = 0; //플레이어 점수합, 음수 총합, 양수 총합
		
		//input
		for(int i = 0; i < N; i++) {
			int t = sc.nextInt();
			if(t < 0) {
				narr[nidx++] = t;
				nsum += t;
			}
			else {
				parr[pidx++] = t;
				psum += t;
			}
		}
		
		//초기 점수합 구하기
		ans = (psum * pidx) + nsum;
		
		Arrays.sort(narr, 0, nidx);	 //음수배열 들어있는 만큼 정렬
		
		//점수합 갱신하기
		pCnt = pidx;	//양수배열 총개수
		for(int i = nidx-1; i >= 0; i--) {	//음수를 하나씩 양수쪽으로 넘김
			pCnt++;
			nsum -= narr[i];  //개인 음수팀 합: 나중에 총합에서 뺄 것
			psum += narr[i];
			
			ans = Math.max(ans, psum * pCnt + nsum);
		}
		
		System.out.println(ans);
		sc.close();
	}

}