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

 

이 문제는 처음에 푼 풀이에서, 몇 가지가 시간 초과가 떴다.

 

내가 처음 생각했던 풀이는

가장 작은 패턴을 찾고, 그 안에서 좌표평면에 따라 겹치는 사각형의 갯수를 구한 뒤에 이를 전체 패턴 갯수만큼 곱하는 방식이었으나,

 

가장 작은 패턴을 찾기 위해 최대공약수가 필요한데, 최대공약수가 매우 큰 수 일 경우, 겹치는 사각형을 구하는 과정에서 하나 하나 하다 보니까 이중 포문에 의해 시간초과가 발생할 수 있었다 (w, h <= 1억)

 

 

그래서 풀이를 찾아봤는데, 아직도 난해하다.

여러가지를 하다 보면 패턴에서 겹치는 사각형의 갯수가 w + h - 1 이 나온다는데,

이게 무슨.. 그냥 매직넘버의 느낌으로 다가온다 ㅜ

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    
    while(b != 0) {
        int temp = a;
        a = b;
        b = temp % b;        
    }
    
    return a;
}

long long solution(int w,int h) {
    
    long long gcdValue = gcd(w, h);
    
    long long wG = w / gcdValue;
    long long hG = h / gcdValue;
    
    return (long long)w * (long long)h - (wG + hG - 1) * gcdValue;
    
}

 

 

---

영 아닌 것 같고, 다른 풀이를 하고 싶어서 찾아봤고

좀 더 좋은 풀이를 이뤄낼 수 있었다.

#include <cmath>

using namespace std;

// 아무래도 숫자가 크다 보니 테케 오류 가능성이 더 높은 것 같다

long long solution(int w,int h) {
    long long answer = 0;
        
    for(long long i = 0; i < w; i++) {
        
        answer += floor(i * h / w);
    }
    
    return answer * 2;
}

주의할 점은, 처음에 h / w 를 통해 기울기를 먼저 구해놨다가 이를 i에 곱하는 형식으로 했는데

나누기를 먼저 이렇게 한 다음에 곱하기를 하면 미세한 오차값이 나왔고, w와 h의 맥스값이 1억이기 때문에 오차가 발생할 가능성 또한 높았다.

 

그래서 6번 테스트 케이스만 자꾸 실패했는데, 이를 고치기 위해선 위와 같이 i와 h를 먼저 곱하게 한 뒤에 w로 나눠줬더니 됐다.