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

문제 링크:

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

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

 

w * h  크기의 직사각형이 주어집니다. 좌측 상단에서 우측 하단으로 대각선을 쭉 긋고, 대각선이 닿지 않은 사각형의 개수를 구하는 문제입니다.

 

문제의 그림을 보면 힌트를 얻을 수 있습니다.

 

문제에서 주어진 예시 그림

그림을 보시면, 흰색 바탕의 같은 패턴이 총 네 번 반복되는 것을 알 수 있습니다.

각 패턴은 주어진 큰 직사각형과 마찬가지로 좌상단-우하단에 대각선이 지나고 있습니다.

따라서 해당 패턴이 총 몇 번 등장하는지, 한 패턴당 몇 개의 칸 위로 대각선이 지나는지 알 수 있으면 답을 쉽게 구할 수 있을 것입니다.

 

각 패턴의 영역 (좌상단-우하단이 만드는 작은 직사각형)을 자세히 봅시다.

위 문제에서 각 패턴은 가로 2칸, 세로 3칸으로 이루어진 직사각형을 형성합니다.

주어진 w, h는 각각 8, 12입니다. 그리고 패턴이 반복된 횟수는 총 4번이죠.

8, 12를 각각 4로 나누면 2, 3을 얻게 됩니다. 즉 4는 8과 12의 최대공약수 (GCD, greatest common divisor)입니다.

최대공약수는 유클리드 호제법을 통해 구할 수 있습니다.

 

다음으로, 패턴 내부를 분석해 봅시다.

내부 패턴은 (w / gcd) * (h / gcd)개의 grid로 이루어져 있습니다.

대각선은 좌상단에서 우하단으로 지나며, 가로로 (w / gcd)만큼, 세로로 (h / gcd)만큼 이동하게 되며,

이동을 할 때의 시작점은 같으므로 중복으로 세어지기 때문에 1을 빼 줍니다.

즉 패턴 내부에서 대각선에 영향을 받는 grid의 수는 (w / gcd) + (h / gcd) - 1이 됩니다.

 

따라서 주어진 문제의 답은,

전체 grid의 수를 구하고, gcd를 구한 다음, 각 영역에서 대각선의 영향을 받는 grid의 수를 구하고, 이를 gcd만큼 곱한 후 전체 grid의 수에서 빼면 됩니다.

 

한 가지 조심할 점이라면, 자료형이 되겠습니다.

w, h는 int형으로 주어지고 답은 long long 형이 되는데, w * h 가 int의 범위를 넘어가는 경우 문제가 생길 수 있습니다.

 

채점 결과

쉽지 않지만 재밌는 문제였던 것 같습니다 ㅎㅎ