멀쩡한 사각형

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

문제 설명

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

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한 사항

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

입출력 예

풀이

def solution(w,h):
    num_of_all_square = w * h
    sum_of_w_h = w + h

    while w % h:
        temp = w
        w = h
        h = temp % h

    return num_of_all_square - (sum_of_w_h - h)

해결 과정

1. 아, 뭔가 규칙이 있을 것 같은데......
   알고리즘 문제는 어떤 규칙을 찾는다면, 문제의 난이도가 쉽게 바뀌는 경우가 많다. (예를 들어, 프로그래머스 - 키패드 누르기)

   이번 문제도 그런 문제 유형일 것이라 생각해 규칙을 찾아보고자 했다.

2. 여러 경우 나열해보기
   문제에서 주어진 테스트 케이스는 하나뿐이다. 이 한 가지만 가지고는 도저히 규칙을 찾을 수 없기 때문에 직접 여러 사각형의 경우를 생각해보았다. 물론, 큰 수로 하면 그리기가 힘드니, 작은 사각형을 생각해보았다.

   그리고 찾은 모든 경우, 전체 사각형 수에서 몇 개가 줄었는지 노트에 써보면서 규칙을 찾고자 했다.

   8 x 12 사각형 : 96개 -> 80개 (16개 감소)
   2 x 2 사각형 : 4개 -> 4개 (2개 감소)
   3 x 3 사각형 : 9개 -> 6개 (3개 감소)
   4 x 3 사각형 : 12개 -> 6개 (6개 감소)

3. 이 규칙이면 할 수 있지 않을까?
   이렇게 나열하고 보니 한 가지 규칙을 찾을 수 있었다.

   1. W와 H를 더한다.
   2. 그 값에서 W와 H의 최대공약수를 뺀다.
   3. 그 값을 전체 사각형 개수에서 뺀다.

   이렇게 하면, 위에서 든 예시의 모든 사각형의 경우를 해결할 수 있다.

다른 사람의 풀이

from math import gcd
def solution(w,h):
    return w * h - (w/gcd(w, h) + h/gcd(w, h) - 1) * gcd(w, h)

python은 다음과 같이 최대공약수를 구하는 모듈을 제공하고 있다. (가져다가 사용하는 것도 실력이다.)