[백준 10819 - Node.js] 차이를 최대로

🔗 문제 링크

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

10819번: 차이를 최대로

✏️ 풀이

const stdin = require('fs').readFileSync('/dev/stdin').toString().trim();
const [N, ...A] = stdin.split(/\s/).map(Number);

const solve = () => {
  let max = 0;
  const permutation = [];
  const selected = Array(N).fill(false);
  const recursion = () => {
    if (permutation.length === N) {
      let sum = 0;
      for (let i = 0; i < N - 1; i++) {
        sum += Math.abs(permutation[i] - permutation[i + 1]);
      }
      if (max < sum) {
        max = sum;
      }
    } else {
      for (let i = 0; i < N; i++) {
        if (selected[i]) {
          continue;
        }
        permutation.push(A[i]);
        selected[i] = true;
        recursion();
        permutation.pop();
        selected[i] = false;
      }
    }
  };
  recursion();
  console.log(max);
};

solve();

가능한 모든 경우 중에서 최댓값을 구하였다.

 

모든 경우를 탐색하는 방법은 아래와 같다.

 

1. for문을 돌면서 N개 중 아직 선택되지 않은 수를 하나 고르고(permutation에 push), 그 수가 이미 선택되었음을 selected를 갱신하여 표시한다.

2. 수를 하나 선택했으면 재귀호출을 통해 위 과정을 반복한다.

3. 만약 이미 N개의 수가 선택되었다면 N개의 수에 대해서 연산을 한 결과값을 max와 비교하여 최댓값을 갱신한다.

4. 재귀호출이 끝나면 직전에 선택한 수를 선택해제한다. (permutation에서 pop하고 selected도 갱신)

5. N!의 모든 경우를 다 탐색하고 모든 재귀호출이 종료된다.