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

 

문제

 

---

풀이방법

 

처음엔 

function solution(w, h) {
    if (w === h) return (w * h) - w;
    if (w > h) return (w * h) - h * 2;
    if (h > w) return (w * h) - w * 2
}

이런식으로 입출력 예만 보고

2개씩 연결되기 때문에 길이가 적은 곳의 두배를 사용하지 못할 것이라고 생각했다..

 

하지만 다른 예 (예를 들어 3 * 5)를 들어보니 맞지 않는다는 것을 알았고

 

반복하는 패턴에 집중하여 생각해 보았다.

 

 

위의 문제에 예를 보면 4개의 박스를 하나로 보고 4번 연속으로 겹치는 것을 알 수 있다.

 

이 블록은 2 * 3 크기이며 넓이가 8이고 높이가 12일때니까 두개를 4로 나눴을 때 2 * 3이 된다.

 

???? 근데 4는 최대공약수?? 가 된다?

---

 

그럼 예를 보았을 때 최대공약수로 나눈 값들이 4개가 들어있고 거기서 8개를 뺀다.

 

최대공약수: gcd

 

(8/ gcd) * (12 / gcd) * gcd - 8  이렇게만 하면 규칙성이 너무 없다고 생각되었다.

 

---

 

그래서 대각선을 보고 생각해보았다.

 

대각선은 결국 가로와 세로의 처음과 끝으로 가기를 원한다. 

 

그럼 결국은 가로 + 세로인데 둘의 처음으로 시작하는 사각형이 똑같다. (그래서 -1 )

 

2 * 3의 식이라고 정해졌을 때 w + h - 1이 되는 것이다.

 

그럼 다시 입출력 예로 와서

 

8 + 12 - 1 이 아니라 그 관련된 식이 4개가 나온다.

 

gcd = 4 이므로 w와 h의 최대공약수가 1이 아닌 사각형은

 

(가로 + 세로 - gcd ) 가 되는 것이다.

 

그럼 결론적으로 식은 가로 * 세로 - (가로 + 세로 -gcd)가 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

그래서 코드를 이렇게 짜주었다.

 

 

---

programmers.co.kr/learn/courses/30/lessons/62048

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