백준 - 3차원 막대기 연결하기

✏️ 백준 - 3차원 막대기 연결하기(19950번)

---

다각형의 변의 길이 조건을 적용하는 것이 포인트!

💭 코드 설계

---

문제 해결의 단계는 아래와 같다.

1. N으로 막대기 개수, start로 시작점, end로 끝점, lines 배열로 막대기들의 길이를 저장한다.
2. 시작점과 끝 점 사이의 거리를 계산하여 distance에 저장한다. (피타고라스 정리를 활용한다.)
3. 만약 막대기가 1개라면, distance와 막대기의 길이가 같아야만 한다.
4. 막대기가 2개 이상이라면, distance를 포함한 가장 긴 변의 길이가 나머지 길이의 합보다 작거나 같아야한다. 따라서 distance를 lines 배열에 넣고, max에 최댓값을 저장한 다음, 최댓값을 뺀 나머지 값들의 합을 최댓값과 비교한다.

🅰️ 제출한 답

---

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

  // 막대기 1개 = 점과 점 사이의 거리(선)
  // 막대기 2개 이상: 가장 긴 변의 길이 <= 나머지 길이의 합

  const N = Number(input[1][0]); // 막대기 개수

  const start = input[0].slice(0, 3).map(Number); // 시작점
  const end = input[0].slice(3, 6).map(Number); // 끝점
  const lines = input[2].map(Number); // 막대기들

  const distance = Math.sqrt((end[0] - start[0]) **2 + (end[1] - start[1])**2 + (end[2] - start[2])**2);

  if(N === 1){
    if(lines[0] === distance){
      console.log("YES");
    }else{
      console.log("NO");
    }
  } else{
    lines.push(distance);
    const max = Math.max(...lines);
    const restLines = lines.filter((line)=> line !== max);
    const restSum = restLines.reduce((acc, cur) => acc+cur, 0);

    if(max <= restSum){
      console.log("YES");
    }else{
      console.log("NO");
    }
  }

💡 해설

---

이 문제를 처음 접했을 때, 솔직히 문제가 잘 이해가 되지 않았다. 처음에는 테스트 케이스의 패턴을 분석해보려고 시도했으나 예제3에서 힌트를 얻었다.
막대기가 2개라면 시작점과 끝점의 거리를 포함해서 선이 3개가 나온다. 시작점과 끝점을 이어야하므로 결국 삼각형을 만들 수 밖에 없는 구조이다. 삼각형을 만들기 위한 각 변의 길이 조건은 가장 긴 변이 나머지 두 변의 합보다 작아야한다. 그러나 우리는 시작점과 끝점을 잇는 것이 목표이기 때문에 나머지 두 변의 합과 가장 긴 변이 같아져도 완전히 포개어져서 가능하다.
막대기가 3개 이상이어도 과정은 같다. 결국 가장 긴 변이 나머지의 합보다 작아져야 다각형을 만들 수 있는 구조가 되기 때문에 이와 비슷한 패턴으로 접근해서 풀었다.

🤔 소감

---

개강을 하고 바빠서 정말 오랜만에 제대로 풀어보는 문제였다. 나는 문제의 난이도에 겁을 먹기 싫어서 난이도를 보지 않고 푼다. 이번 문제가 골드 문제라는 소리를 스터디에서 들었는데 생각보다 어렵지 않게 푼 것 같아서 뿌듯하다. 개강이라는 핑계를 대지 않고 스터디원들과 화이팅해서 문제풀이에 열중할 것이다.