멀쩡한 사각형

멀쩡한 사각형

2020.08.01

const getGreatestCommonDivisor = (a, b) => {
  if (!b) {
    return a;
  }
  return getGreatestCommonDivisor(b, a % b);
};

const solution = (w, h) => {
  return w * h - (w + h - getGreatestCommonDivisor(w, h));
};

• 기울기로 풀어보려고 끙끙대다가 도저히 안 돼서 결국 질문하기를 참조해서 풀었다 ㅠ

• 이 문제는 가로와 세로의 길이를 서로소로 만드는 게 핵심인 듯하다.

• 최대공약수로 나눠 가로와 세로의 길이를 서로소로 만들고, 좌측 상단에서 우측 하단으로 선이 지나가면서 가로선을 (가로선의 길이 - 1)만큼, 세로선을 (세로선의 길이 - 1)만큼 지난다.

• 선을 한 번씩 통과할 때마다 손상되는 정사각형이 1개씩 늘어나기 때문에 결국 (가로선의 길이 - 1) + (세로선의 길이 - 1)이 되는데, 여기서 맨 처음 시작하는 정사각형은 포함되지 않았기에 최종적으로는 (가로선의 길이 - 1) + (세로선의 길이 - 1) + 1이 된다.

• 여기에 다시 최대공약수를 곱해주면 전체 손상된 정사각형의 수가 나오는 것이었다.
  (이걸 어떻게 생각하냐)