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

# 문제 원문

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.제한사항

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

입출력 예

W / H / result

8

12

80

 

# 문제 풀이

도형에 관한 문제로 규칙을 찾아야하는데 규칙을 찾는게 어려운 문제이다. 대각선으로 자른다는 조건 때문에 자르는 부분에 걸리는 사각형들 갯수를 특정짓기 어렵기 때문이다. 문제 자체는 주어진 w, h 의 곱이 원래 사각형의 총 갯수이니 w * h에서 잘린 사각형을 빼서 반환하면 된다. h만큼의 사각형은 무조건 빠지고(당연히 한칸씩은 무조건 빠진다.) w에 따라서 여러개의 사각형이 빠지는 구간이 있는데 이 부분의 규칙을 고민해도 알아 낼 수 없어서 팁을 확인후 최대 공약수와 관련 되어 있다는 것을 알고 도움 받았다. 솔직히 수학 문제 그중에서도 기하에 관한 문제가 아닌가 싶고, 문제 난이도 자체는 말그대로 수학적 능력에 따라 달라진다. 기하문제의 경우 규칙을 찾을 경우 최대 공약수 와 최소 공약수와의 관계를 구하는게 일반적인 접근법으로 보이니 기억해두자.

 

# 솔루션 플로우

1. 입력 받은 w * h의 합에서 w+h를 빼준후 w,h의 최대 공약수를 구해서 더해준다.

2. 얻어진 result를 반환한다.

1. GCD 를 활용한 풀이

function solution(w, h) {
    return w * h - (w + h) + gcd(w, h);

    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
}