📝 PROGRAMMERS - 멀쩡한 사각형

문제

PROGRAMMERS Level 2 - 멀쩡한 사각형

접근 방법

내가 처음 구현했던 풀이는 (0,0)(0, 0)(w,h)(w, h)를 잇는 직선의 방정식을 만들어 kk가 자연수 일 때 y=ky = k일 때의 xx좌표를 구해 제외해야하는 사각형을 구했다. 하지만 이렇게 풀면 시간초과가 난다.

결국 풀지 못해서 슈퍼짱짱님의 풀이를 참고했다. 설명을 정말 잘 해주셔서 내 설명보다는 이 분의 설명을 읽는 것을 더 추천하다!

설명

normal-square

너비가 4이고 높이가 6인 사각형이 있다. 이 사각형의 왼쪽 아래를 (0,0)(0, 0)으로 두고 (0,0)(0, 0)(4,6)(4, 6)을 지나는 선을 그리면 다음과 같다. 이 선은 (0,0)(0, 0)(4,6)(4, 6)외에도 (2,3)(2, 3)도 지난다.

이 때 원점을 제외한 직선이 지나는 점(= 빨간 사각형)의 개수는 2개 즉, 4와 6의 최대공약수임을 알 수 있다.

결론

wwhh의 최대공약수가 1인 경우 직선이 지나는 점은 (0,0)(0, 0)(w,h)(w, h)외에는 없다. 즉 사각형 전체가 빨간 사각형이 된다. 이 사각형에 대각선을 그리면 너비와 높이의 개수 만큼의 사각형을 지난다. 이 때 공통으로 지나는 사각형이 있으므로 1을 빼면, 제외되는 사각형의 개수는 w+h1w+h-1이 된다.

wwhh의 최대공약수가 1보다 클 때는 앞의 예시처럼 최대공약수의 개수만큼의 빨간색 사각형이 존재한다. 이 때 이 빨간색 사각형의 최대공약수는 1이므로 앞의 공식을 이용하여 빨간 사각형 내에서 제외되는 사각형의 개수를 구하고 빨간색 사각형의 개수만큼 곱해주면 된다. 즉, wwgg의 최대공약수가 gcdgcd일 때, 제외되는 사각형의 개수는 gcd(w/gcd+h/gcd1)=w+hggcd * (w/gcd + h/gcd - 1) = w + h - g이다.

교훈

여러 모양의 사각형을 그려보면서 규칙을 구하려 했는데 눈에 보이는 규칙이 없어서 결국 다른 분의 풀이를 참고하였다. 알고리즘 문제라기 보다는 수학 문제에 가까운데 여태까지 풀었던 수학 문제 중 최대공약수최소공배수를 이용한 문제들이 꽤 있었다. 비슷한 문제가 나온다면 최대공약수최소공배수를 의심해봐야겠다.

소스 코드

import math

def solution(w,h):
    gcd = math.gcd(w, h)
    if gcd == 1:
        return w*h-(w+h-1)
    return w*h-(w+h-gcd)

👋@코딩하는펭귄
파이썬과 웹에 관심 많은 컴공 전공자

GitHubInstagramTIL