백준 3020 개똥벌레

문제

3020번: 개똥벌레

 

풀이

결론부터 본다면 구간별로 장애물을 파괴한 개수를 배열에 담은 후, 최소가 되는 값과 그 값의 개수가 답이 됩니다.

 

위와 같이 문제가 주어질 때 4 구간에 장애물이 파괴되기 위한 조건으로는 아래와 같습니다.

1. 종유석의 경우 높이가 4보다 크거나 같아야 한다.
2. 석순의 경우 전체 높이에서 4를 뺀 것보다 1 이상 커야 한다.

즉 4 구간의 장애물이 파괴한 개수 = 종유석이 높이 4보다 크거나 같은 갯수 + 석순이 전체 높이에서 4를 뺀 것보다 1 이상 큰 개수가 되는 것입니다.

 

과정

1. 석순과 종유석 각각의 배열에 해당 높이의 개수가 몇 개인지 입력받아줍니다.

let W, H;
let top = []; // 석순
let bot = []; // 종유석
let idx = 0;

rl.on('line', function (line) {
  if(!W) {
    [W, H] = line.split(' ').map(n => +n);
    top = Array.from({ length: H + 1 }, () => 0);
    bot = Array.from({ length: H + 1 }, () => 0);
  } else {
    if(idx % 2 === 0) {
      bot[+line]++;
    } else {
      top[+line]++;
    }
    
    if(++idx === W) rl.close();
  }
})

2. 부분 합을 통해 전체 높이를 기준하여 역으로 높이가 n보다 크거나 같은 개수를 배열에 담아줍니다.

원리는 간단합니다.

n의 높이보다 크거나 같은 장애물의 갯수 = n + 1보다 크거나 같은 갯수 + n의 높이 개수입니다.

  let sum_top = [];
  let sum_bot = [];
  let cnt = 0;

  for(let i = H; i > 0; i--) {
    sum_top[i] = (sum_top[i + 1] ?? 0) + top[i];
    sum_bot[i] = (sum_bot[i + 1] ?? 0) + bot[i];
  }

3. 2번 과정에서 증류석이 각각의 높이보다 크거나 같은 개수를 정리하였으므로, 거기서 석순이

전체 높이에서 각각의 높이를 뺀 것보다 1이 더 큰 높이 개수를 더해줍니다. 

 

동시에 

2 ≤ N ≤ 200,000이기 때문에 최솟값을 max(200,000) 값으로 할당해줍니다.

최솟값이 되는 개수를 출력하기위해 최솟값을 할당하고 갯수를 count 해줍니다.

  let cnt = 0;
  let min = 200000;

  for(let i = H; i > 0; i--) {
    sum_bot[i] = sum_bot[i] + sum_top[H - i + 1];

    if(sum_bot[i] < min) {
      min = sum_bot[i];
      cnt = 1;
    } else if(sum_bot[i] === min) {
      cnt++;
    }
  }

 

최종 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let W, H;
let top = []; // 석순
let bot = []; // 종유석
let idx = 0;

rl.on('line', function (line) {
  if(!W) {
    [W, H] = line.split(' ').map(n => +n);
    top = Array.from({ length: H + 1 }, () => 0);
    bot = Array.from({ length: H + 1 }, () => 0);
  } else {
    if(idx % 2 === 0) {
      bot[+line]++;
    } else {
      top[+line]++;
    }
    
    if(++idx === W) rl.close();
  }
})

.on('close', function () {
  let sum_top = [];
  let sum_bot = [];
  
  for(let i = H; i > 0; i--) {
    sum_top[i] = (sum_top[i + 1] ?? 0) + top[i];
    sum_bot[i] = (sum_bot[i + 1] ?? 0) + bot[i];
  }
  
  let min = 200000;
  let cnt = 0;

  for(let i = H; i > 0; i--) {
    sum_bot[i] = sum_bot[i] + sum_top[H - i + 1];

    if(sum_bot[i] < min) {
      min = sum_bot[i];
      cnt = 1;
    } else if(sum_bot[i] === min) {
      cnt++;
    }
  }

  console.log(min, cnt);
  process.exit();
});