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

-


문제설명


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


Idea 01

풀이 방법이 직관적으로 떠오르지 않아 정의된 문제에 대한 규칙을 찾아보기로 했습니다. 
방법은 아래와 같이 파워포인트 표에 대각선을 직접 대입하여 단순 무식하게 규칙을 찾았습니다.
1. 정사각형일 때
각 w에 해당하는 길이 만큼 격자칸이 잘리는걸 알 수 있습니다.
사용할 수 있는 격자칸은 w==h라면 w * h - w


2. 직사각형일 때
2씩 넘어갈 때 마다 격자칸이 +2가 되는걸 알 수 있습니다.

3의 배수에 맞춰 중앙 값이 +1 높은걸 알 수 있습니다.

하지만
w가 4로 바뀌었을 때, w가 2일 때와 비교하여 규칙을 찾기가 쉽지 않았습니다.


Idea 02

유의미한 규칙을 찾아낼 수 없어 다른 사람들의 접근법을 확인했습니다.


1. 좌표계로 표현
w=6, h=8인 그림의 직선의 식은 \(y=\frac{8}{6}x=\frac{4}{3}x\)이며, (3,4), (6,8)일 때 위 그림상에 빨간점을 지납니다.
이 때 직선이 지나는 빨간점의 수는 w, h의 최대공약수와 동일합니다. (gcd=2, 빨간점 2)


멀쩡한 사각형에 나온 예시 w=8, h=12인 경우 직선의 식은 \(y=\frac{12}{8}x=\frac{3}{2}x\)이며, (2,4),(4,8),(6,8),(8,12)일 때, 위 빨간점을 지나며 점 4개의 수는 w, h의 최대공약수와 동일한 것을 확인할 수 있습니다. (gcd=4, 빨간점 4)


2. 수식 정의

gcd와 빨간색 점 수가 동일하다는 것을 기반으로 대각선에 포함되는 사각형의 개수를 찾아낼 방법을 모색합니다.


아래 그림을 보면 빨간점 사이 직사각형 안에 포함되는 사각형의 개수가 동일한 것을 알 수 있습니다.
빨간점 점 사이 포함되는 사각형의 개수 * gcd는 전체 대각선에 포함된 사각형의 수임을 알 수 있습니다.

빨간점 사이 포함되는 사각형의 개수는 \(\frac{w}{gcd} + \frac{h}{gcd}-1\) 수식으로 구할 수 있습니다.

구하는 방식은 다음과 같습니다.
전체 사각형의 크기가 w=2, h=3이라 가정하면, 대각선은 반드시 w와 h의 길이만큼 움직입니다. ((0,0)에서 (w,h)까지 대각선이 그려지기 때문)

대각선이 w 방향과 h 방향으로 움직이면서 포함되는 사각형을 차례대로 세어보면 다음과 같습니다.
※ w 방향으로 움직이면서 사각형을 셀 때를 '\', h 방향으로 움직이면서 사각형을 셀 때를 '/'로 표기했습니다.
위 그림에서 보면 (0,0)에 해당되는 부분을 중복되게 셈을 합니다. (사각형이 X로 표기)
따라서 w=2, h=3일 때 대각선에 포함되는 사각형의 개수는 w+h-1 (중복제거)이 되는 것을 확인할 수 있습니다.

정리하면,
빨간점 사이 포함된 사각형의 개수(w+h-1) * gcd를 하면 전체 대각선에 포함된 사각형의 수를 구할 수 있습니다.

즉, 특정 w, h가 주어지면, \((\frac{w}{gcd} + \frac{h}{gcd} - 1) * gcd\)가 대각선에 포함되는 모든 사각형의 개수이고, 
위 수식을 정리하면 w + h - gcd가 됩니다.

문제에서는 대각선에 포함되지 않은 사각형의 수를 반환해야 하므로, w * h - (w + h - gcd)가 됩니다.

최대한 쉽게 설명하고자 했는데, 이해가 가지 않으시면 직접 손으로 그려보면 좋을 거 같습니다.
그래도 이해가 가지 않으면 질문 부탁드립니다.


Solution
import math


def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a


def solution(w, h):
    if h < w:
        w, h = h, w
    n = gcd(w, h)
    # n = math.gcd(w, h)
    return w * h - (w + h - n)
math의 gcd를 사용하는 방법이 있지만, 저는 공부 목적이기 때문에 커스텀으로 만들어서 사용했습니다.


전체 코드는 아래 깃허브에서 확인 가능합니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

[opencv-python] 이미지 크기조절(resize) 하는 법

-
이미지
이미지 크기 조절(resize) 이미지 크기를 조절하는 예제를 알아보겠습니다. 이미지 불러오기 import cv2 img = cv2.imread( "image/cat.jpg" ) cv2.imshow( "img" , img) cv2.waitKey() cat.jpg 이미지를 불러와 화면에 띄웁니다. 이미지 크기 조절 img = cv2.imread( "image/cat.jpg" ) print ( "img.shape = {0}" .format(img.shape)) resize_img = cv2.resize(img , ( 300 , 300 )) print ( "resize_img.shape = {0}" .format(resize_img.shape)) cv2.imshow( "img" ,  img) cv2.imshow( "resize img" , resize_img) cv2.waitKey() # 출력 # img.shape = (360, 480, 3) # resize_img.shape = (300, 300, 3) 이미지 크기 조절 방법 1 - cv2.resize(img, dsize=(300, 300)) cv2.resize(원본 이미지, 결과 크기 이미지)로 이미지의 크기를 조절할 수 있습니다. 결과 크기 이미지는 Tuple이며 (width, height)의 형식 입니다. 이미지 크기 조절 방법 2 - cv2.resize(img, dsize=(300, 300), interpolation=cv2.INTER_AREA) cv2.resize(원본 이미지, 결과 크기 이미지, 보간법)로 이미지 크기를 조절할 수 있습니다. 보간법은 이미지의 크기를 변경하면 변경된 이미지의 픽셀 사이의 값을 결정해야 하는데, 이때 보간법을 사용합니다.
자세한 내용 보기

[python]파이썬: csv reader header skip (첫번째 행 무시하기, 안읽기)

-
이미지
header를 skip하기 위해서는 next() 를 하면 됩니다. ex) 아래와 같은 데이터를 가지는 excel 파일에서 header를 skip 했을 때와 하지 않았을 때를 비교 해보겠습니다. next()를 사용하지 않았을 경우 next()를 사용했을 경우 연관문헌 pandas 특정 행에 값 넣기 https://daewoonginfo.blogspot.com/2019/04/pandas.html 참고자료 https://evanhahn.com/python-skip-header-csv-reader/
자세한 내용 보기

[python] selenium close와 quit 차이점

-
이미지
close와 quit 차이점 selenium webdriver를 닫는 기능으로는 close()와 quit()이 존재합니다. close() close()는 현재 selenium webdriver가 활성화되어 있는 화면만을 종료 합니다. 2개 이상의 webdriver 탭이 열려있다면 현재 활성화되어 있는 webdriver만 종료되고 나머지 webdriver는 종료되지 않습니다. 현재 열려있는 webdriver close() -> 활성화되어 있던 naver만 종료가 되었음. close() 이후 탭 전환을하고 싶으신 분은 아래의 링크를 참고하세요. window, mac에서 새 탭 열기 및 전환 https://daewoonginfo.blogspot.com/2019/05/python-selenium.html quit() quit()는 dispose() 함수를 불러와 열려있는 모든 webdriver를 종료하고 세션을 안전하게 종료 합니다. 프로그램을 종료할 때 quit()을 사용하지 않는다면 webdriver 세션이 완벽하게 종료되지 않아 메모리 누수가 발생할 수 있습니다. 하나의 webdriver가 열려있다면 close()와 quit() 어느 것을 사용해도 동일한 작업을 수행 합니다. 하지만 2개 이상의 webdriver가 열려있다면 close()와 quit() 다르게 작동  하는것을 유의해야합니다. 참고문헌 [1] https://www.zyxware.com/articles/5552/what-is-close-and-quit-commands-in-selenium-webdriver
자세한 내용 보기