[알고리즘C++]멀쩡한사각형

오늘의 문제

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

멀쩡한사각형

나의 풀이

[풀이 1]

#include<iostream>
using namespace std;

long long gcd(long long a, long long b){
	while(b!=0){
		long long r = a%b;
		a= b;
		b= r;
	}
	return a;
}

long long solution(int w,int h) {
    long long answer = (long)w*h;
    int g = gcd(w, h);
    w = w/g;
    h = h/g;
    if(w == h)
        answer = answer - w * g;
    else
        answer = answer - (w + h-1) * g;
    
    return answer;
}

모범 정답

#include <iostream>
using namespace std;

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

long long solution(int w,int h)
{
   long long answer = 1;

    int gcd = GCD(w, h);
    cout << w + h - gcd;
    answer = ((long)w * h) - ((long)w + h - gcd);

   return answer;
}

using namespace std;

long long solution(int w, int h) {
    long long answer = 0;

    for (int i = 0; i < w; ++i) {
        answer += (int)((double)h*i/w);
    }

    return 2 * answer;
}

배울 점

• GCD를 저렇게 짤 수 있네 외워야 겠다.
• 억끼리 곱하는것을 double형변환을 통해서 해결하는구나.
• 두번째 모범정답처럼 빈칸을 세는게 아니라 남는것을 세어 곱하는 방법이 있다. 와.