[프로그래머스][유클리드호제법][C++] 멀쩡한 사각형

멀쩡한 사각형

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

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

문제 설명

가로길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자 칸은 1cm x 1cm 크기입니다.

이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다.

그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다.

새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한 사항

• W, H : 1억 이하의 자연수

풀이 방법

유클리드 호제법을 이용해 최소공배수를 구하고 패턴을 찾아 계산하는 문제이다.

우선 그림을 보면 선이 일정한 간격을 두고 꼭짓점을 지나는데, 최소공배수 만큼의 간격을 두고 지나간다.

즉, 가로와 세로를 최소공배수로 나눈 작은 단위의 직사각형에서 패턴을 찾은 다음 계산하면 되겠다고 생각했다.

이후 계산식을 찾긴 했는데 솔직히 왜 이렇게 되는지 이유는 잘 모르겠다.

몇 가지 사각형을 그려보며 계산해본 결과 width와 height를 기존 가로와 세로의 길이에서 최소공배수로 나눈 값이라고 했을 때,

작은 직사각형에서 대각선에 의해 지워지는 사각형의 갯수는 width + height - 1이다.

최종 계산식은 answer = w * h - (width + height - 1) * gcd이다.

참고로 w * h를 할 때 (long long)으로 형변환을 해줘야 정답 처리가 된다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    return a;
}

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

    int x = gcd(w, h);

    int width = w / x;
    int height = h / x;

    answer = answer - (width + height - 1) * x;

    return answer;
}