Programmers - 멀쩡한 사각형

---

title: Programmers - 멀쩡한 사각형
date: 2022-06-28
tags:

• Algorithm

---

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

문제 요약

1억 이하의 정수인 w와 h로 이루어진 사각형이 존재한다. 1 단위 격자로 나뉘어 있으며, 한 꼭지점과 대각선 꼭지점을 잇는 선분에 맞추어 자르면 잘린 정사각형은 사용할 수 없다. 사용 가능한 남은 부분의 개수를 return한다.

문제 풀이

w와 h 각각 1억 이하이며, 서로소 혹은 소수로 인해 작은 사각형으로 분리할 수 없는 상황이 생긴다. 이로 인해 O(n)밖에 노릴 수 없다.
기울기에 맞추어 어느 정사각형이 잘리는지 count한다.
만약 작은 격자의 꼭지점을 지나면 w와 h의 최대공약수가 1이 아니라는 뜻이며, 현재 구하고 있는 사각형의 크기로 w와 h로 이루어진 사각형을 나눌 수 있다는 소리다. 그때까지 구한 잘린 정사각형의 수를 간단한 연산과 함께 처리해주면 1억개를 전부 셀 필요 없이 정답을 찾을 수 있다.

이렇게 수학과 관련된 큰 반복이 필요한 문제는 일반화를 시키는 것이 가장 중요하다. 문제를 풀고 다른 풀이를 확인하고 나서야 일반화를 시킬 수 있었다.
선분이 격자들의 경계(꼭지점)을 지나지 않을 경우, 잘리는 정사각형은 w + h - 1 이다.
꼭지점을 지날 때마다 해당 일반화 식에서 1씩 빼야 하며, 이는 결국 최대공약수와 관계가 있음을 알 수 있다.
결국 잘린 정사각형의 개수는 w + h - w와 h의 최대공약수 이다.

프로그램

long long solution ( int w ,int h )
{
    long long answer = 0 ;
    int iFormer = 0 ;
    int iCurret = 0 ;
    double dTemp = 0 ;



    for ( int i = 1 ; i <= w ; ++i )
    {
        iCurret = dTemp = ( long long ) h * i / ( double ) w ;

        if ( iCurret == dTemp )                    // Find small rectangle to split
        {
            answer += iCurret - iFormer ;

            answer *= w / i ;

            break ;
        }

        ++ iCurret ;
        answer += iCurret - iFormer ;
        iFormer = iCurret - 1 ;
    }

    return ( long long ) w * h - answer ;
}