알고리즘(C++) / 프로그래머스 level 2 : 멀쩡한 사각형

level 2 : 멀쩡한 사각형

https://programmers.co.kr/learn/courses/30/lessons/62048?language=cpp 

코딩테스트 연습 - 멀쩡한 사각형

코드

//프로그래머스 멀쩡한 사각형
#include <iostream>
using namespace std;

int GCD(int w, int h) {
    if (w % h == 0)
        return h;
    return GCD(h, w % h);
}

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

    answer = (long long)w * h - ((long long)(w + h) - gcd);

    return answer;
}

int main() {
    int w = 8;
    int h = 12;
    cout << solution(w, h) << "\n";
    return 0;
}

 

설명

(잘린 사각형) =  (가로의 길이) + (세로의 길이) - (가로 세로의 최대공약수) 와 같은 공식을 찾아낼 수 있다.

예) w=2, h=3 이면

x
x	x
	x

x 표시한 부분이 잘리게 된다. 잘린 사각형 = 2+ 3 -1 =4이다. 

 

고찰

처음에 공식을 찾지 못하여 일차방정식으로 지나가는 사각형을 찾아 문제를 풀었었다.

검색하여 공식을 찾아보니 다음과 같은 규칙이 있었고 이번 문제에서 이런 규칙을 알지 못했으면 풀지 못했을거 같다. 

더 공부하고 규칙을 찾으면서 공부해야할 거 같다.