[프로그래머스] 멀쩡한 사각형

문제 설명

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

 

제한 사항

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

 

입출력 예

W       H         result

8

12

80

 

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/62048?language=java

---

생각보다 쉬운 문제고 생각보다 어려운 문제 같습니다. 일단 제가 찾은 규칙은 복잡하기만 하고 시간도 오래 걸릴 뿐더러 일단 틀렸습니다. 너무 어렵게 생각했습니다. 한동안 손을 놓다가 다시 하려고 하니까 감 자체가 없군요. 이 문제를 고민해봤다면 최대 공약수를 이용하게 되고, 최소 단위가 반복된다는 사실을 알게 됐을 겁니다. 규칙 찾는 게 어렵고 찾으면 그다음부터는 쉽습니다. 최소 블록 단위가, 예시에서는 2 * 3입니다. 8과 12의 최대 공약수는 4입니다. 최소 단위 블록이 4번 반복됩니다. 최대 공약수 만큼 반복됩니다. 최대 공약수는 라이브러리를 사용해도 되고 직접 구현해도 됩니다. 직접 만드는 게 더 나을 수 있습니다. 유클리드 호제법을 검색해보세요. 어렵지 않습니다.

 

최소 블록 단위에서의 규칙만 찾으면 될 것 같습니다. 2 * 3에서 잘린 사각형은 그림에서 보듯이 4개입니다. 이렇게 생각해보면 어떨까요. 저 점선은 최소 단위 블록의 가로 세로의 개수만큼 지납니다. 가로 방향으로 2개 세로 방향으로 3개의 정사각형을 지난다는 의미가 됩니다. 2와 3을 더하고 시작하는 정사각형 하나를 빼면 4가 나옵니다. 가로 방향으로 3개가 겹친 것 아니냐(최하단을 포함)는 생각이 들 수 있지만, 가로 크기인 2의 범위 안에서 생각해야 올바른 답이 나올 수 있습니다. 그렇게 생각해야 세로 만큼을 더할 수 있습니다. 3 * 4으로 놓고 봐도 이 공식이 적용됩니다. 점선은 가로 + 세로 만큼 정사각형을 잘라냅니다. 겹치는 시작 부분의 개수 하나만 빼주면 되는 것입니다. 6입니다.

 

이제 문제 전체에 해당하는 공식을 만들면 됩니다. 이건 쉽습니다. 최소 블록 단위에서 잘려진 정사각형의 개수는 가로 + 세로 - 1로 구할 수 있었습니다. 그럼 최소 단위에서의 가로 세로는 어떻게 구할까요? 언급했듯이 최대 공약수를 이용하면 됩니다. 주어진 w과 h를 각각 최대 공약수로 나누면 최소 블록 단위의 가로, 세로가 나옵니다. 그렇게 해서 구한 잘린 정사각형 개수에 다시 최대 공약수를 곱하면 잘린 정사각형의 총합이 나옵니다. 식을 다음과 같이 세울 수 있습니다.

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

-> w + h - gcd

마무리는 코드로 확인하십시오. 그리고 문제에서 제한사항이 W, H가 1억 이하의 자연수로 주어졌기 때문에 solution 메서드의 파라미터는 int가 아니라 long으로 변경해야 합니다. 

class Solution {
	public long solution(long w,long h) {
        long lgcd = gcd(w, h);
        long answer = w * h - (w + h - lgcd);
        return answer;
	}
    
     public long gcd(long a, long b) {
        if (b == 0) {
            return (long)a;
        }
        return gcd(b, a%b);
    }
}