[코딩연습9일차] 프로그래머스 : 멀쩡한 사각형 / python

요 며칠은 자소서를 쓴다고 코딩연습을 못 했다.

사실 자소서 별 것도 아닌데,, 쓸 때마다 스트레스 받고 기분이 안 좋아서ㅋㅋㅋ

차마 코딩연습까지 하고 싶지 않았다.

나태한 나를 반성반성ㅠㅠ💦

오늘도 Lv.2로 바로 때려보자!!

---

문제 설명

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

제한사항

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

입출력 예

W	H	result
8	12	80

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

---

나의 해설 >>

아, 지금 정보처리기사를 공부하고 있어서 안 사실인데ㅋㅋㅋㅋ(비전공자라 기초이론 모름ㅠㅠ)

프로그래밍이란 의뢰 → 의뢰 분석 → 알고리즘 →코딩 →결과물 의 과정을 거친다는 것.

그래서 "코딩연습 = 알고리즘을 세우고 코딩하기" 였던 것이다.

지난번에 왜 코딩연습 하는지 모르겠다 해놓고 깨달았음ㅋㅋㅋㅋㅋㅋ

이 해설하는 부분이 바로 알고리즘 세우는 부분인 것이었던 것이었던 것이다.후후 잡소리 엿습니다!

 

아니 이거 수학문제야? ;; 문과생인 나로써는 짜증짜증이었던 문제 ㅋㅋㅋㅋㅋㅋㅋ

 

1. 그림을 그냥 (x,y)의 좌표위의 함수로 생각한다고 하면

2. (0,0)(w,h)를 지나는 일차함수를 그릴 수 있다 = 그 함수가 대각선

3. 기울기의 크기 (=h/w)에 따라 안에 몇개의 점이 그려지는 지 알 수 있고, 이 위치가 최대공약수 위치임.

• 예를들어, 위에 나온 예시의 경우는 (0,0)(8,12) 좌표를 지나는 함수이고
• 8과12의 최대공약수 = 4
• 그리고 8/4인 x축으로 2칸, 12/4 y축으로 3칸마다 격자선을 지난다.  
  (2와3 얘네를 서로소라고 불렀었지 수학시간에)
• 잘려진 가로길이 2, 세로길이 3인 직사각형을 다시 생각해보면 얘네의 최대 공약수는 1이다.
• 이 경우에는 대각선이 지나는 정사각형 갯수는 (가로길이 + 세로길이 - 1) 이다. ,,,, ☞노가다를 통해 알아냄...^_^
• 그렇기 때문에! 총 대각선이 지나는 정사각형 갯수는"""(w/최대공약수 + h/최대공약수 - 1) * 최대공약수"""" 이다.

4. 그렇다면  최대공약수를 구한 뒤, result = w*h - [w/최대공약수 + h/최대공약수 - 1) * 최대공약수]

 

---

하지만 여기서부터 멘붕 ㅠ 최대공약수를 대체 어케 구해야하나 미친럼이네 하다가

결국 검색을 하게 되고,, 다른 분들 푼 걸 통해서 gcd함수를 알게 되었따.

 

그래서 최고 효율로 쓴 답은 이거...

from math import gcd

def solution(w,h):
    return w * h - (w/gcd(w, h) + h/gcd(w, h) - 1) * gcd(w, h)
    
    #gcd(x,y)를 하면 x,y의 최대 공약수를 구해준다.
    #그렇기 때문에 gcd(w,h)는 직사각형 너비&높이의 최대 공약수를 구한 것.