2024.04.25목 멀쩡한 사각형의 갯수 구하기

학부생시절 꾸준히 했던 코테. 게을러서 안했더니 다시 실력이 한참 모자라졌다..

알고리즘 문제를 처음부터 풀어보다가 아무리 코테를 안했어도 처음은 너무 기본적이 문제밖에 없어서 뒤에서 부터 풀어 보기로 했다.

 

 

멀쩡한 사각형의 갯수 구하기

 

 

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

 

• 문제 풀이 과정

 

최대 공약수 만큼 일정한 패턴의 사각형이 반복되는 구조. 처음 봣을 때 괜히 반복되는 공식을 찾으려고 했다가 시간을 날렸던 것 같다. 

 

위에 주어진 w =8 , h = 12인 사각형을 예시로 들면

이렇게 생긴 사각형이 8과 12의 최대 공약수인 4 만큼 반복되는 것을 알 수 있다. 

이 사각형에서 사용 가능한 사각형의 수는 2 

 

 

 

다른 예시 ( w =5 , h =15)

 

5와 15의 최대 공약수는 5.

 

이러한 모양의 사각형이 5번 반복되는 것을 알 수 있다.

 

 

이제 각 패턴의 사각형에서 제외되는 사각형의 수를 구하면 된다.

 

 

예시 하나 더 ( w=8 , 6)

6과 8의 최대공약수는 2. 같은 패턴의 사각형이 2번 반복될 것이다.

 

해당 모양의 사각형이 두 번 반복되고 이 때 사용할 수 없는 사각형의 수는 6

 

다시한번 사용할 수 없는 사각형의 예시를 나열하면

 

사용 불가능한 사각형의 개수는 

가로 + 세로 -1 

 

의 패턴인 것을 알 수 있다.

반복되는 패턴의 갯수와, 그 패턴안에서 사용할 수 없는 사각형의 갯수를 알았다면 이제 코드로 옮기기만 하면  끝이다.

 

 

 

먼저 최대 공약수 구하기 ( 유클리드 알고리즘 사용)

int GetGCD(int a,int b)
{
	while(b!=0)
    {
    	int temp = a % b ;
        a = b;
        b = temp;
    }
    return a;
}

 

 

그리고 전체 사용 가능한 사각형의 갯수에서 사용 불가능한 사각형을 빼면 끝이다.

 

멀쩡한 사각형 = (전체 사각형) - ( (각 패턴단위 사각형 당 사용 불가능한 사각형의 개수) X (최대 공약수) )

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

    long long gcd = GetGCD(w,h);
    
    answer =(long long)w*h - (((w/gcd)+(h/gcd)-1)*gcd);
    return answer;
}

 

 

 

잘 나오는 것을 알 수 있다.

 

 

 

주의

 

 answer =w*h - (((w/gcd)+(h/gcd)-1)*gcd);

처음에 그냥 이렇게 했다가 테스트 케이스 통과를 못했다. w와 h 는 int형 변수이기 때문에 두 수를 곱했을 때 범위를 넘어갈 수 있는 케이스가 있으므로 long long으로 캐스팅을 해 주어야 한다.