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

기울기를 구해서

i-1일 때 y값과 i일때 y값을 비교하며 각각의 개수를구해서 더하려고했다.

계속해서 틀린값이 나왔다.

JAVA로 풀려니 type에 의하여 정말 복잡해졌다

---

javascript

동적타입을 가진 자바스크립트를 사용한다면

너무나 간단해진다.

function solution(w, h) {
    let l=h/w;
    let count=0;
    for( let i=1;i<=w;i++){
        count+=Math.ceil(l*i);
    }
    return (w*h-count)*2;
}

다른 풀이를 찾아봤다.

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

최대공약수를 이용한 풀이였다.

• w,h의 최대공약수를 구한다.
  • w를 최대공약수로 나눈 값 → w'
  • h를 최대공약수로 나눈 값 → h'
  • 즉, w'마다 h'개의 사각형을 사용하지 못하게 된다.
• 왜냐하면 w' 마다 일정 패턴을 나타나는 걸 볼 수 있다. 예를들면, w가 8, h가 12인 경우 → 최대공약수는 4다
  
• w'은 2고 h'은 3이 된다. 따라서, 2x3 직사각형의 패턴을 볼 수가 있다.
  • 이런 직사각형이 최대공약수 g개 만큼 나타나게 된다.

( 이는 위의 링크를 타고 들어가면 그림으로 확실하게 알 수가 있다. )

이 직사각형 내부에서, 점선이 지나가는 직사각형의 개수는 몇개일까?

• 무조건 w'+h'-1임 을 알아차릴 수가 있다.
• 최대공약수가 1이던, 1보다 크던
• g * ( w' + h' -1 ) 임을 알 수 있다.

---

JAVA에서 최대공약수 구하는 방법

• 1부터 시작하여, w,h중 더 작은 값까지의 수로, 두 수를 나눠본다.
• 두 수가 모두 나누어떨어지는 경우 g값을 update한다

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        long g = (long) gcd(w,h);
        long wp = w/g, hp = h/g; 
        
        answer = ((long)w*h) - g*(wp + hp -1);
        return answer;
    }
    
    public int gcd(int w, int h ){
        int min = Math.min(w,h);
        int g =1;
        for(int i=1;i<=min;i++){
            if( w % i == 0 && h % i == 0 ){
                g = i; 
            }
        }
        return g; 
        
    }
}