백준 27277 장기자랑

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

문제

실력의 합이 최대가 될 수 있게끔 공연순서를 배치하는 조합론 문제이다. 나올 수 있는 모든 경우의 수 중에 가장 실력의 합이 최대가 되는 것들을 골라야 하다보니 백트래킹을 이용해서 완전탐색하고 여기서 최댓값을 업데이트 시킬수도 있겠지만, 병사의 수가 100000까지 가다보니 1초 안에 모든 조합을 구하기는 어려워보인다.

그렇다면 그리디가 조금 더 좋은 접근방식으로 보인다. 1 2 3 4 5 6이 있다고 했을 때, 가장 크게 나올 수 있는 수는 번갈아서 큰수, 작은수대로 하면 가장 합이 큰 수를 만들 수 있다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const n = +inputs[0];
const peoples = inputs[1].split(" ").map(Number);
 
peoples.sort((a, b) => a - b);
 
//p를 위한 포인터
let pleft = 0;
let pright = n - 1;
let idx = 0;
const p = new Array(n);
const copy = new Array(n);
 
while (pleft <= pright) {
  if (idx % 2 === 0) {
    p[idx] = peoples[pright];
    copy[idx] = peoples[pright];
    pright--;
  } else {
    p[idx] = peoples[pleft];
    copy[idx] = peoples[pleft];
    pleft++;
  }
  idx++;
}
 
for (let i = 1; i < n; i++) {
  p[i] = Math.max(p[i] - copy[i - 1], 0);
}
 
const sum = p.reduce((acc, cur) => acc + cur, 0);
console.log(sum);
 

작은수, 큰수를 번갈아서 줘야 하므로 해당 값을 고를 투포인터가 필요하다. 해당 포인터로 작은수는 pleft, 큰 수는 pright에서 가져와서 할당한 뒤 마지막에 최댓값을 계산해주었다.