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

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

프로그래머스

 

 

1. 해결방법

직사각형이 있다면 대각선으로 가로질렀을 때 선과 접하는 부분을 제외한 사용 가능한 부분의 개수를 구해야 한다.

 

먼저 자료형에 대해 생각해야 한다.

반환해야 하는 자료형은 long인데 매개변수는 모두 int로 주어졌다.

연산을 하는 과정에서 w와 h가 계속 필요한데 그때마다 캐스팅이 불편하니 처음부터 형변환을 시켜주었다.

 

이후에, 예시 그림을 보면 8(가로), 12(세로)를 최대공약수로 나누었을 때 (2,3)이 나온다.

(2,3)을 계속 +1씩 곱해나가보면 (4,6), (6,8), (8,12)이다. 이는 선과 만나는 좌표다.

 

그래서 최대공약수가 1인 (2,3)부터 보면 총 6개 박스에서 4개가 사용 불가능이다.

2(가로) + 3(세로) - 1(최대공약수) = 4(사용 불가능 박스 개수) 가 나온다. 확실하지 않아 (4,6)도 보겠다.

최대공약수 1

 

아래 그림을 보면 규칙적으로 진행된다는 것을 알 수 있다.

위 수식을 그대로 적용시켜보자.

4(가로) + 6(세로) - 2(최대공약수) = 8(사용 불가능 박스 개수) 가 정확히 나온다.

최대공약수 2

 

위 수식을 코드로 적용하면 w * h - (w + h - 최대공약수)이다.

 

수식 다음으로 최대공약수구하는 방법이 어려웠는데 작은 값으로 큰 값을 나눠주면서 값을 바꿔나가다 보면 최대공약수를 구할 수 있다. 최대공약수를 구하는 메소드를 따로 빼서 연산에 더해주었다.

 

 

2. 정답코드

def solution(w,h):
    import math
    return (w * h) - (w + h - math.gcd(w, h))

규칙은 어렵지 않지만 그 규칙을 이용한 공식 찾는 것이 어려웠다. 특히나 "가로 + 세로 - 최대공약수"의 공식을 찾지 못해서 while문으로 하드코딩 작성으로 하였지만 실패하고 말았다...

확실히 규칙 문제는 하나씩 쪼개가면서 해야할 것 같다. 그리고 최대공약수와 최소공배수 그리고 //, % 등등 많은 연산을 대입해보고 규칙을 찾아야 할 것 같다.

그리고 파이썬 math 라이브러리에서 gcd와 lcm 메서를 알게 되었다.