인프런 커뮤니티 질문&답변

최근에 다시 자바스크립트로 돌리면서, 기존에 파이썬으로 했던 것들 다시 모두 자바스크립트로 풀어보면서 문제 풀어보니, 발견했습니다.

이거 첫번째 가정을, 그리디로 접근하면 해결 안되는 문제인것같습니다. 이후 가정들은 당연히 그리디 관념으로 최적값 찾을 수 있는데, 첫번째 가정부터 그리디로 접근하면 해결되는 문제가 아니라서 어긋나기때문에, 그리디관념이 통하지 않는 문제인것같습니다.

완전탐색해버리거나, 시간 더 줄이려면 백트래킹 가지치기 해야하는 문제인것같습니다.

입력입니다!

7

172 67

183 65

179 61

178 62

177 63

170 72

181 60

기존 풀이(무조건 183선발) 가 내주는 답 : 3

감독 현수가 원할 것 같은 답 : 6

그리디로 가장 키 큰 사람 무조건 선발하는 과정이 풀이에서 오류인것같습니다.

183 선발 가정하고 cnt 값 구하고,

그다음 181 선발 가정하고 cnt값 구하고,

쭉 다음 순으로 선발 가정하고 cnt값 구하는데,

만약 어떤 사람 선발 가정하고 cnt값 구하는데

남은 사람 수 다 합해도 기존 Max cnt보다 적을 경우,

백트레킹 가지치기로 break 혹은 return 끊어버리는게 맞는것같습니다.

풀이1. 이중포문

const input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split("\n");

const n = parseInt(input[0]);
const arr = Array.from(Array(5), () => []);
for (let i = 0; i < n; i++) {
  arr[i] = Array.from(input[i + 1].trim().split(" ")).map((v) => parseInt(v));
}

function solution(n, arr) {
  arr.sort((a, b) => b[0] - a[0]);

  let cnt = 0;
  let largest = 0;
  let res = 0;
  for (let i = 0; i < n; i++) {
    largest = arr[i][1];
    cnt += 1;
    if (res >= n - i) {
      break;
    }
    for (let j = i + 1; j < n; j++) {
      if (arr[j][1] > largest) {
        largest = arr[j][1];
        cnt += 1;
      }
    }
    res = Math.max(res, cnt);

    cnt = 0;
  }

  console.log(res);
}

solution(n, arr);

 풀이2. DFS

const input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split("\n");

const n = parseInt(input[0]);
const arr = Array.from(Array(5), () => []);
for (let i = 0; i < n; i++) {
  arr[i] = Array.from(input[i + 1].trim().split(" ")).map((v) => parseInt(v));
}

let cnt = 0;
let res = 0;
//const list = [];

function DFS(s, weight) {
  if (s < 0) return;

  if (cnt + n - s <= res) {
    cnt -= 1;
    s -= 1;
    return;
  }

  for (let i = s; i < n; i++) {
    if (arr[i][1] > weight) {
      cnt += 1;
      //list.push(arr[i][1]);
      DFS(i + 1, arr[i][1]);
      //list.pop();
    }
  }

  res = Math.max(res, cnt);
  //console.log(list);
  cnt -= 1;
}

function solution(n, arr) {
  arr.sort((a, b) => b[0] - a[0]);

  DFS(0, 0);

  console.log(res);
}

solution(n, arr);