안녕하세요 리뷰복습하다가, 발견했습니다

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

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

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

입력입니다!

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);