프로그래머스 - 멀쩡한 사각형 (Lv.2)

문제 링크

• 👉 멀쩡한 사각형

문제 설명

• W x H 크기의 격자가 주어질 때, 아래와 같이 대각선을 그었을 때 선이 지나는 칸은 사용할 수 없는 사각형이다.
• 사용할 수 있는 사각형의 개수를 구하라.

문제 접근

• W 와 H 의 최대공약수를 구한 후 이를 나누어 주어 기울기를 구할 수 있다. y = x(b/a) 형태
• 원점을 지나는 직선이라고 생각하고, x=1 ~ x=a-1 까지 위 함수의 값을 구한다.
• 함수의 값보다 큰 정수에 위치하는 칸은 사용할 수 없는 칸이 된다.

구현(All Pass)

#include <iostream>
#include <algorithm>
using namespace std;

long long a, b;

double func(long long x){
    double ret = (b*x) / (double)a;
    return ret;
}

long long solution(int w,int h) {
    long long answer = 0;
    long long total = (long long)w * h;
    
    // 최대공약수 찾기
    long long small = min(w, h);
    long long mCommon = 1; // 서로소인 경우 1
    for(long long i=2; i<=small; i++){
        if(w%i==0 && h%i==0) mCommon = i;
    }
    a = w / mCommon;
    b = h / mCommon;
    long long area = 0;
    if(b%a==0){
        area = h;
    }
    else{
        area = a*b;
        long long tmp = 0;
        for(long long i=1; i<a; i++){
            double val = func(i);
            tmp += (long long)val;
        }
        area -= (tmp*2); // 대칭 빼주기
        area *= mCommon;
    }
    answer = total - area;
    return answer;
}

보완사항

• 최대공약수(GCD)는 유클리드 알고리즘 으로 구현한다.
  • 임의의 두 자연수 a,b가 주어졌을 때, a를 큰 값이라고 가정한다.
  • a를 b로 나눈 나머지를 n 이라고 할때, n이 0이면 b가 최대공약수가 된다.
  • n이 0이 아니라면 a에 b를 넣고, b에 n을 넣은 후 위 과정을 반복한다.

구현 - Updated

#include <iostream>
#include <algorithm>
using namespace std;

long long a, b;

double func(long long x){
    double ret = (b*x) / (double)a;
    return ret;
}

int GCD(int a, int b){
    if(a%b==0) return b;
    return GCD(b, a%b);
}

long long solution(int w,int h) {
    long long answer = 0;
    long long total = (long long)w * h;
    
    // 최대공약수 찾기
    int gcd = GCD(w,h);
    a = w / (long long)gcd;
    b = h / (long long)gcd;
    
    long long area = a*b;
    long long tmp = 0;
    for(long long i=1; i<a; i++){
        double val = func(i);
        tmp += (long long)val;
    }
    area -= (tmp*2); // 대칭 빼주기
    area *= (long long)gcd;
    answer = total - area;
    return answer;
}