[프로그래머스][Javascript] 멀쩡한 사각형

---

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다.

 

그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

---

제한사항

• W, H : 1억 이하의 자연수

---

입출력 예

W	H	result
8	12	80

 

 

---

입출력 예 설명

입출력 예 #1

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

---

문제 설명

그림을 한번 살펴봅시다.

3 X 1 의 사각형 일 경우 3개의 사각형을 지나게 됩니다.

 

3 X 2 사각형일 경우 4개의 사각형을 지나게 됩니다.

 

3 X 3 사각형 일 때는 3개 의 사각형을 지나게 됩니다.

 

자!!! 이제 어떠한 규칙인지 아시겠나요?

저는 솔직히 처음엔 이게 어떠한 규칙인지 사실 몰랐습니다.

(만약 이 규칙을 알아 차리셨다면 대단합니다. 부럽네요)

그래서 구글의 힘을 빌려 해당 블로그에서 힌트를 얻었고 그것을 바탕으로 설명 드리겠습니다.

 

사실은 저러한 대각선이 지나는 사각현 갯수를 구하는 공식이 따로 있다고 합니다.

(링크 참고)

 

그 공식은

사각형의 가로 + 사각형의 세로 - (사각형의 가로, 세로 최대공약수)

입니다.

 

즉,

W + H - (W, H의 최대 공약수)

라는 것이지요.

 

자 그럼 이제 이 최대공약수는 어떻게 구해야 할까요?

최대공약수를 구할때는 유클리드 호제법이라는 방식을 사용하면 됩니다.

유클리드 호제법을 잘 모르겠다구요?

 

그렇다면 예를 들어 설명해 보죠

 

예를들어 3과 5의 최대 공약수를 구한다고 생각해 봅시다.

3의 약수는 [ 1, 3 ] 

5의 약수는 [ 1, 5 ]

입니다.

그렇기 때문에 둘의 공통 약수 중 가장 큰수는 1입니다.

 

그렇다면 이 1이라는 수를 어떻게 구해야 할까요?

그것은 바로 유클리드 호제법을 사용하여 구현할 수 있습니다.

아래 그림을 보시죠

 

유클리드 호제법은 W 와 H를 나눈 값의 나머지가 0이 나올때 까지 반복하여 0이 나올 경우 0이 나올 수 있었던 H를 반환하는 행위 입니다.

 

혹시 모르니 그림에 대한 설명을 드리자면 아래와 같습니다.

 

1. 3 % 5 의 나머지가 3이므로 W에 5를 넣고 H에 3을 넣어 나머지를 구합니다.
2. 5 % 3 의 나머지가 2 이므로 W에 3를 넣고 H에 2을 넣어 나머지를 구합니다.
3. 3 % 2 의 나머지가 1 이므로 W에 2를 넣고 H에 1을 넣어 나머지를 구합니다.
4. 2 % 1 의 나머지가 0 이므로 H인 1을 반환합니다.

어때요 이해가 가시나요?

그래도 이해가 안가신다구요?

그렇다면 코드로 한번 보시죠.

// 유클리드 호제법을 이용한 최대 공약수 구하기
function gcd(w, h) {    // 처음 W와 H를 받습니다.

    // W와 H의 나머지를 구합니다.
    const mod = w % h;

    // 만약 나머지가 0일 경우 H를 반환합니다.
    if (mod === 0) {
        return h;
    }

    // 만약 0이 아닐경우 W에 H를 넣고 H에 나머지인 mod를 넣어 해당 함수를 다시 호출해 줍니다.
    return gcd(h, mod);
}

어때요, 잘 이해가 가시나요?

이렇게 gcd를 구했으면 해당 문제는 다 해결된 것 입니다.

 

위에서 설명했듯이

W + H - (W, H의 최대 공약수)

이 공식을 사용하면 되기 때문입니다.

 

---

소스코드

// 유클리드 호제법을 이용한 최대 공약수 구하기
function gcd(w, h) {    // 처음 W와 H를 받습니다.

    // W와 H의 나머지를 구합니다.
    const mod = w % h;

    // 만약 나머지가 0일 경우 H를 반환합니다.
    if (mod === 0) {
        return h;
    }

    // 만약 0이 아닐경우 W에 H를 넣고 H에 나머지인 mod를 넣어 해당 함수를 다시 호출해 줍니다.
    return gcd(h, mod);
}


function solution(w, h) {
    // 최대 공약수를 구해줍니다.
    const gcdVal = gcd(w, h);

    // 공식에 맞춰 사용
    return w * h - (w + h - gcdVal);
}

console.log(solution(8, 12))

---

마치며

이번 문제는 공식을 몰랐다면 아예 풀지 못하는 문제였고,

Level 2 치고는 꽤 어려웠습니다만,

소스코드는 진짜 심플 합니다.

 

아직 제가 미숙하단것을 많이 느끼는 문제네요...

만약 문제가 잘못되었거나, 질문이 있으신 분들은 댓글을 남겨주세요

감사합니다.