[Programmers] 멀쩡한 사각형

▶ 문제 : https://programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

 

▶ 코드 : 

function solution(w, h) {
    const total = w * h;
    const g = gcd(w, h); // g 즉, 최대공약수는 대각선으로 나누었을때 반복되는 사각형형태가 등장하는 횟수이다.
    const miniSquare = w/g + h/g - 1; // 각각의 작은 사각형은 가로를 g로 나눈값과 세로를 g로 나눈값에서 1(중복해서 자르는 사각형)을 뺀 값만큼 사각형을 지운다.
    
    return total - (g * miniSquare);
}

function gcd(a,b){
    if(b === 0){
        return a;
    }else{
        return gcd(b, a % b);
    }   
}

 

 

▶ 문제 풀이 : 

- 해당 문제는 '멀쩡한 사각형 풀이' 를 참고하여 풀이하였다.

1. 전체 사각형에서 잘리는 사각형의 수를 세어야 한다. (이때, 전체사각형은 직사각형이라는 전제조건이 문제에 있다.)

2. 전체 사각형에서 잘리는 사각형(잘리는 영역)은 반복되는 형태를 가지는데, 이때 반복되는 횟수는 GCD(최대공약수) 번 등장한다. 

3. 추가적으로 잘리는 영역의 작은 사각형이 최대공약수 번 등장한다면 하나의 작은 영역 사각형 내부에서 잘리는 사각형의 개수는 어떻게 구할까? 

  - 작은 사각형의 크기는 (w // g) * (h // g) 이다. 이때 각각의 사각형에 대해 대각선을 그었을때 (작은 사각형의 가로) 개, (작은 사각형의 세로) 개 씩 나눈다. 하지만 이때 가로와 세로에 대해 중복으로 카운팅하는 칸(처음 시작칸) 에 대한 1을 빼주어야한다. 

4. 지금 까지의 말을 정리해보면 전체 사각형의 크기 (w * h) 에서 gcd(작은 사각형의 등장 횟수) * miniSquare(작은 사각형에서 대각선에 의해 제외되는 사각형의 수)를 빼주어야 하고 miniSquare의 수는 "(w / g) + (h /g) - 1" 이 된다는 것이다. 

5. 따라서 전체 식은 `(w * h) - gcd * (w/g + h/g - 1)` 이 되어야 한다는 의미이다. 

6. gcd() 함수는 '유클리드 호제' 를 참고해 구현하였으며 각각을 조합하여 결과를 출력해주면 되는 문제였다.