백준2891 - 카약과 강풍 (탐욕법) node.js

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

문제 해결 방식

각 팀마다 보유한 카약의 갯수를 먼저 저장해두었다. 이후 상황에 따라 최선의 선택을 하는 탐욕법으로 접근하였는데, 기초 논리는 다음과 같다.

만약 자신의 보유한 카약의 갯수가 2로 부족한 팀에게 배를 줄 수 있으며 이웃된 팀 모두 배가 필요하다면, 자신의 앞번호부터 배를 주는 방식으로 선택했다.

이와 같은 방법을 통해, 문제에서 제시된 '다른 팀에서 받은 카약을 다른 팀에 빌려줄 수 없다'를 만족할 뿐더러, 출발하지 못하는 팀 역시 최소화할 수 있다.

 

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [[N, S, R], broken, rest] = data.map((el) => el.split(" ").map(Number));

  const check = Array.from({ length: N }, () => 1);

  broken.forEach((el) => check[el - 1]--);
  rest.forEach((el) => check[el - 1]++);

  for (let i = 0; i < N; i++) {
    if (check[i] == 2) {
      if (0 < i && !check[i - 1]) {
        check[i]--;
        check[i - 1]++;
      } else if (i < N - 1 && !check[i + 1]) {
        check[i]--;
        check[i + 1]++;
      }
    }
  }

  console.log(check.filter((el) => !el).length);
}

solution(input);