[Summer/Winter Coding(2019)] 멀쩡한 사각형 C++

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

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

 

 

- 직사각형의 대각선이 가로지르는 사각형들은 일정한 패턴이 반복된다.

이 패턴이 반복되는 횟수가 가로 세로의  GCD

  -> GCD(12, 8) = 4

- 이 패턴의 가로 세로 길이가 각각 w / gcd, h / gcd 이다.

  -> 8 / 4 = 2, 12 / 4 = 3

- 대각선이 지나는 칸은 한줄에 1칸 ~ 2칸 존재할 수 있다.

- 대각선이므로 세로줄기준 최소 1칸은 차지할수 밖에 없다.

  -> h / gcd = 12 / 4 = 3

- 하지만 가로줄기준 2칸을 차지하는 경우는 w/gcd -1 이다.

  -> w / gcd - 1 = 8 / 4 -1 = 2 - 1 = 1

 

=> 최종식

- w * h - [ { ( w / gcd ) + ( h / gcd ) - 1 } * gcd ]

- w * h - ( w + h - gcd )

 

 

 

 

 

- GCD구현하기 (유클리드호제법)

        long long a=W, b=H, c;
        
        while (b != 0) {
            c = a % b;
            a = b;
            b = c;        }

        long long gcd = a;

 

- 제출코드 (가로, 세로가 int로 주어지기때문에 계산시 형변환 해주거나 변수 재설정)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

    long long W = w;
    long long H = h;

    if (w == h) {
        answer = (W * H) - W;
    }

    else {
        long long a=W, b=H, c;
        
        while (b != 0) {
            c = a % b;
            a = b;
            b = c;
        }

        long long gcd = a;

        answer = (W * H) - (((W / gcd) + (H / gcd) - 1) * gcd);
    }


    return answer;
}

int main() {
    cout << solution(8, 12);//80
	
    return 0;
}