2Level / Summer/Winter Coding(2019) / 멀쩡한 사각형

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/62048#

프로그래머스

 

문제 풀이 방법

이 문제에서 사용하지 못하는 사각형의 갯수를 구하는 것이 중점인 문제였다.

이 로직은 초등학교 경시대회에서도 나온 로직이다....(초등학생들 대단해....)

 

로직은 최대 공약수를 구하는 것이 핵심이였다.

(전체 단위 블럭 갯수) - (가로 + 세로 - (가로 세로의 최대공약수)) 가 대각선이 지나는 단위 블럭의 갯수이다.

 

예외 처리는 2개로 처리했으며 각각 가로 세로가 같은 경우와 가로 혹은 세로 중 한개의 길이가 1인 경우이다.

가로 세로가 같은 경우는 정사각형이며 대각선이 가로(혹은 세로)의 길이만큼 단위 블럭을 지난다.

가로 혹은 세로 중 한개의 길이가 1인 경우는 대각선이 모든 블럭을 지난다.

 

코드

const solution = (w, h) => {
    let answer = 0;
    const getGcd = (a, b) => a % b === 0 ? b : getGcd(b, a%b);
    // 가로 혹은 세로가 1이면 모든 블럭이 사용할 수 없기 때문
    if(w === 1 || h === 1) return 0;
    // 가로 세로가 같으면 정사각형이므로 가로 혹은 세로의 길이 만큼의 갯수만 빼주면 됨
    else if(w === h) return (w * h) - w;
    
    else return (w * h) - (w + h - getGcd(w, h));
}