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

1. 기울기를 알고 있으니, 이 기울기를 이용해서 하나씩 헤쳐가며, 해당되는 사각형 갯수를 세서, 

*2를 하려고 했는데 몇 개 틀린 문제들이 있네... 

class Solution {
    public long solution(int w, int h) {
        long answer = 0;
        double m = -(double)h/w;
        for(int i= 1;i<=w;i++){
            double count = (m * (double)i)+h;
            answer+=count;
        }
        
        return answer*2;
    }
}

테스트 1 〉	통과 (0.08ms, 72.8MB)
테스트 2 〉	통과 (0.15ms, 78.6MB)
테스트 3 〉	통과 (0.06ms, 75.3MB)
테스트 4 〉	통과 (0.15ms, 75.7MB)
테스트 5 〉	통과 (0.10ms, 78.2MB)
테스트 6 〉	통과 (0.27ms, 73.4MB)
테스트 7 〉	통과 (0.21ms, 74.1MB)
테스트 8 〉	통과 (0.02ms, 75.5MB)
테스트 9 〉	통과 (0.01ms, 83.2MB)
테스트 10 〉	통과 (0.02ms, 77.6MB)
테스트 11 〉	통과 (464.00ms, 75.6MB)
테스트 12 〉	통과 (461.11ms, 93.9MB)
테스트 13 〉	실패 (45.46ms, 78.2MB)
테스트 14 〉	통과 (242.47ms, 91MB)
테스트 15 〉	실패 (62.82ms, 88.5MB)
테스트 16 〉	실패 (1.44ms, 72.8MB)
테스트 17 〉	실패 (35.14ms, 84.9MB)
테스트 18 〉	통과 (0.03ms, 75.9MB)

2. 결국, 풀이를 보았다.

첫 번째, 생각했던 똑같은 패턴이 최대공약수만큼 반복한다는 문제까지는 접근했는데

그 이후에 패턴을 찾는 것이 어려울 거 같아 포기했는데 조금 더 매달려볼 걸...

=> (w*h ) - (( (w/최대공약수) + (h/최대공약수 ) -1 ) * 최대공약수)

import java.math.BigInteger;

class Solution {
    public long solution(int w, int h) {
        long answer = 0;
        int gcd = BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).intValue();
        answer = (long) w *h - (w/gcd + h/gcd -1) * gcd;
        
        return answer;
    }
}

 

테스트 1 〉	통과 (0.72ms, 71.6MB)
테스트 2 〉	통과 (0.79ms, 67.3MB)
테스트 3 〉	통과 (1.22ms, 74MB)
테스트 4 〉	통과 (0.81ms, 84MB)
테스트 5 〉	통과 (0.79ms, 72.7MB)
테스트 6 〉	통과 (0.72ms, 74.9MB)
테스트 7 〉	통과 (0.71ms, 74.5MB)
테스트 8 〉	통과 (0.68ms, 73.9MB)
테스트 9 〉	통과 (0.96ms, 75.3MB)
테스트 10 〉	통과 (0.72ms, 75.7MB)
테스트 11 〉	통과 (0.75ms, 77.6MB)
테스트 12 〉	통과 (0.55ms, 79.1MB)
테스트 13 〉	통과 (0.44ms, 75.5MB)
테스트 14 〉	통과 (0.39ms, 81.4MB)
테스트 15 〉	통과 (0.55ms, 80MB)
테스트 16 〉	통과 (0.41ms, 77.6MB)
테스트 17 〉	통과 (0.39ms, 73.9MB)
테스트 18 〉	통과 (0.73ms, 69.4MB)