[프로그래머스-JS] level 2 멀쩡한 사각형 (*)

 

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

프로그래머스

 

나의 코드 

 

1) 실패한 코드 

function solution(w, h) {
    const sum = h*w;
    if(w === 1 || h === 1) return 0;
    if(w > h){
        const divide =  w / h;
        return sum - Math.ceil(divide) * h;
    }else if(h > w){
        const divideW =  h / w;
        return sum - Math.ceil(divideW) * w;
    }else{
        return sum - w;
    }
}

 

정확히 반절만 맞았다.

풀고풀고 하다가 1시간이 넘어서 질문하기에서 힌트를 찾았다. 

 

그리고 다시 생각해보았다. 

 

이 선은 직사각형이든 정사각형이든 양 끝점을 가로지른다. 

이는 택시 기하학을 활용해서 풀 수있다는 뜻이다. 

 

최단거리 구하기를 활용하면 된다. 

문제 예제에서는  가로가 8cm 세로가 12cm이기에 

8 + 12 = 20 이고 사용할 수 없는 정사각형은 16개이다.

즉 4개의 오차가 발생한다.  왜그럴까?

 

 

 

자세히 보면 대각선이 꼭지점을 지날때는 네모칸이 끊어져있다. 

그런곳이 총 3곳이고   - 3 을해주면 17이된다. 그리고 여기서 - 1 만 더 해주면 16개가 된다. 

그런데 가만보면  꼭지점 3개 + 1 = 4   이 4는 가로 8 세로 12의 최대 공약수이다. 

 

그렇다면 사용할 수 없는 정사각형의 개수는 ? 

 

12 + 8 - 4 = 16

 

다른 경우도 같은까?

 

 

이 경우에도 10, 8의 최대 공약수는 2이다. 

즉 꼭지점 1 + 1

따라서 사용할 수 없는 정사각형은 

10 + 8 - 2 = 16

 

 

그렇다면 최대공약수가 없다면 ??? 

 

대각선이 만나는 꼭지점이 없다. 

10 , 3의 최대 공약수는 0

 

따라서 사용할 수 없는 정사각형은 

10 + 3 - 0 = 13

 

이걸 식으로 나타내면 

 

문제에서는 사용가능한 정사각형의 개수를 구하라고 했으니까 

 

전체 정사각형의 개수  -  사용할수 없는 정사각형의 개수 

= 가로 x 세로  - ( 택시 기하학 - (w, h)의 최대 공약수)

= w x h   -  ( w + h - gcd )

 

이것을 코드로 나타낸다면 아래와 같다. 

 

2) 성공한 코드 

function solution(w, h) {
    const gcd = (a,b) =>{
        const remainder = a%b;
        if(!remainder) return b;
        return gcd(b, remainder)
    }
    return w*h - (w+h - gcd(w,h))
}

 

다른 사람 코드