[알고리즘]프로그래머스 62048번 - 멀쩡한 사각형

프로그래머스 62048번 - 멀쩡한 사각형

프로그래머스 62048번 - https://programmers.co.kr/learn/courses/30/lessons/62048

 

요구사항

1. 종이를 대각선 꼭짓점 2개를 잇는 방향으로 잘랐을 때 사용할 수 있는 정사각형의 개수를 반환하라.

2. 정사각형은 1cm x 1cm 크기입니다.

 

요구사항 분석 및  풀이과정

1. 위 예를 살펴보면 사용할 수 없는 영역인 흰 영역에 다음과 같이 일정한 패턴이 존재한다는 것을요. 

 

 

그러면 이렇게 생긴 영역의 수는 몇 개인지 어떻게 알 수 있을까요? 간단합니다. 높이/너비의 비율을 보면 됩니다.  위 문제에서 높이는 12, 너비는 8 따라, 비율은 12/8 = (3*4) / (2*4)입니다.

 

너비와 높이가 2:3 비율로 가지는 사각형이 가로로 4개, 세로로 4개 총 16개가 존재한다는 사실을 알 수 있고, 우리가 필요한 대각선 영역에는 4개 존재한다는 사실을 알 수 있습니다.

 

여기서 4가 어떤 수인지 감이 오신 분도 있고, 안 오신 분도 있을 것 같습니다. 여기서 4는 높이(12), 너비(8)의 최대공약수입니다. 왜 최대공약수인지는 위 비율 수식에서 알 수 있을 거라고 생각합니다.

 

그러면 사용할 수 없는 역역인 흰 영역의 개수는 어떻게 알 수 있을까요? 여러 가지 방법이 있을 수 있지만, 저는 빨간 영역의 개수는 알아냈으니, 각 빨간 영역에서의 흰 영역의 수를 구한 다음, 빨간 영역의 개수를 곱하여 총 흰 영역의 개수를 구할 것입니다.

 

그러면 위 빨간 영역에서의 흰 영역의 수를 구해보도록 하겠습니다. 어떻게 구할 수 있을까요 ? 저는 흰 영역을 상단과 하단으로 몰아보고 싶다는 생각을 하였고 몰게 되면 다음과 같습니다.

 

 

이러고, 귀납적으로 한번 개수를 끼워맞춰보도록 하죠. 빨간 영역의 너비를 p, 높이를 q라고 하면, 좌측 상단은 항상 움직이지 않습니다. 그러면 1번째 열로 q-1 개의 흰 영역이 이동하고, 1번째 행으로 p-1 개의 흰 영역이 이동합니다. 좌측 상단은 항상 흰 영역입니다.

 

따라서 각 빨간 영역에서의 흰 영역의 수는 다음과 같습니다.

 

각 빨간 영역에서의 흰 영역의 수 = 1 + (p - 1) + (q - 1) = p + q - 1

각 빨간 영역의 너비  = p

각 빨간 영역의 높이 q

 

왜 그런지 이해가 잘 안 되시는분은 여러 케이스를 그려보시는 걸 추천드립니다. 그러면 빨간 영역에서의 흰 영역의 수는 다음과 같습니다.

 

흰 영역의 수 = 빨간 영역의 수 * 각 빨간 영역에서의 흰 영역 수

 

구하기 앞서, p와 q와 빨간 영역의 수를 전체 사각형의 높이와 너비의 최대 공약수를 이용하여 표현해보도록 하겠습니다.

 

p = 전체 사각형의 너비 / 전체 사각형의 높이와 너비의 최대 공약수 = w / gcd(w, h)

q = 전체 사각형의 높이 / 전체 사각형의 높이와 너비의 최대 공약수 = h / gcd(w, h)

 

각 빨간 영역에서의 흰 영역의 수 = p + q - 1 = w / gcd(w, h) + h / gcd(w, h) - 1

 

빨간 영역의 수 = 전체 사각형의 높이와 너비의 최대 공약수  = gcd(w, h)

 

 

흰 영역의 수

= gcd(w, h) * ((w / gcd(w, h)) + (h / gcd(w, h)) - 1) = w + h - gcd(w, h)

 

위의 식이 이해가 되지 않는다면 우리가 어떤 방법으로 빨간 영역의 패턴을 찾아왔는지를 다시 생각해보시면 좋을 것 같습니다. 그러면 최종적으로 사용할 수 있는 정사각형의 개수는 다음과 같습니다.

 

전체 사각형의 수 = w * h

 

사용할 수 있는 정사각형의 개수

= 전체 사각형의 수 - 흰 영역의 수 = w * h - (w + h - gcd(w, h))

 

소스코드 작성

class Solution {

	public long solution(int w, int h) {
		long totalCount = (long)w * (long)h;
		long eraseCount = (long)w + (long)h - 
        		BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).longValue();
		return totalCount - eraseCount;
	}
}

 

결과

 

소스코드 깃허브 주소

링크