[알고리즘/백준/2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제

---

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

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = n.split(" ").map(Number);
const flavors = arr.map((row) => row.split(" ").map(Number));
let cnt = 0;
// 섞어먹으면 안 되는 조합
const flavorsNotToMix = Array.from({ length: N + 1 }, () =>
  Array(N + 1).fill(0)
);

for (let [a, b] of flavors) {
  flavorsNotToMix[a][b] = true;
  flavorsNotToMix[b][a] = true;
}

for (let i = 1; i <= N; i++) {
  for (let j = i + 1; j <= N; j++) {
    if (flavorsNotToMix[i][j]) continue;
    for (let k = j + 1; k <= N; k++) {
      if (flavorsNotToMix[j][k] || flavorsNotToMix[i][k]) continue;
      cnt++;
    }
  }
}
console.log(cnt);

우선 섞어먹으면 안 되는 조합을 미리 2차원 배열에 저장한다.

아이스크림 종류 중 3가지를 선택하는 조합이무로 3중 for문을 통해 3가지 조합을 선택한다.

이때 섞어먹으면 안 되는 조합을 포함하는 경우, continue한다. 아닌 경우 cnt를 증가시킨다.