📌 프로그래머스 - 멀쩡한 사각형 (수학 / GCD)

Об этом предложении

📌 문제 설명 가로 길이가w, 세로 길이가 h인 직사각형이 있다. 이 직사각형은 작은 정사각형 여러 개로 나누어져 있다. 여기에 👉 왼쪽 아래 모서리부터 오른쪽 위 모서리까지 대각선을 하나 긋는다. 대각선에 걸쳐 있는 정사각형은 사용할 수 없다. 따라서 👉 전체 정사각형 개수에서 대각선에 걸리는 정사각형 개수를 뺀 값 을 구하는 문제이다. 💡 처음 문제를 보고 든 생각 처음에는 w * h 하면 전체 정사각형 개수가 나오니까 그다음에는 "대각선이 지나가느 정사각형만 빼면 되는 거 아닌가?" 라고 생각했다. 이 생각 자체는 맞았다. 🔥 내가 처음 발견한 규칙 예를 들어 w = 8 h = 12 이면 전체 정사각형은 8 * 12이므로 96개이다. 처음 그림을 보고 대각선을 그었을 때 👉 일정한 패턴이 반복되는 것을 발견했다. 특히 8 12 가 4를 기준으로 나누어 졌다. 8 = 4 * 2 12 = 4 * 3 그래서 "아, 대각선이 같은 구조로 4번 반복되는 건가?" 라는 생각을 했다. 그리고 이4가 바로 gcd(8,12) 였다. 🧠 gcd가 뭐였지? import math gcd = math.gcd(w,h) gcd는 👉 최대공약수 이다. 예를 들어 8의 약수 1, 2, 4, 8 12의 약수 1,2,3,4,6,12 둘이 공통으로 가지는 가장 큰 수는 4 이다. 따라서 math.gcd(8, 12) 은 4가 된다. 🔥 핵심 공식 대각선에 걸리는 정사각형의 개수는 broken = w + h - gcd 이다. 처음에는 이 공식이 굉장히 뜬금없이 보였다. 특히 왜 w + h? 왜 gcd를 뺴지? 가 가장 어려웠다. 🔍 왜 w + h를 더할까? 대각선은 직사각형을 지나면서 👉 가로 방향의 격자 경계 👉 세로 방향의 격자 경계 를 만나게 된다. 그래서 기본적으로 가로 쪽 -> w 세로 쪽 -> h 를 세어서 w + h 를 생각할 수 있다. ❗ 그런데 문제가 생긴다 대각선이 가로선과 세로선이 만나는 정확한 격자 교점 을 지나가는 경우가 있다. 예를 들어 ┌──┬──┬──┬──┐ │ │ │ │ │ ├──┼──●──┼──┤ │ │ │ │ │ └──┴──┴──┴──┘ 가운데 ●처럼 대각선이 격자 교점을 정확하게 지나가면 우리가 가로 경계 1번 + 세로 경계 1번 으로 세면서 👉 같은 교점을 2번 센다. 실제로는 하나의 교점이므로 👉 중복을 빼줘야 한다. 🔥 그 중복을 결정하는 것이 gcd 여기서 아까 발견했던 8 = 4 * 2 12 = 4 * 3 가 다시 등장한다. gcd(8,12) = 4이므로 대각선의 구조가 👉 같은 작은 패턴으로 4번 반복된다. 그래서 격자 교점에서 발생하는 중복을 gcd를 이용해서 보정한다. 결과적으로 broken = w + h - gcd가 된다. 🔍 8 × 12에 실제로 적용 w = 8 h = 12 이면 gcd = math.gcd(8, 12) ↓ 4 따라서 broken = 8 + 12 - 4 ↓ 16 즉, 👉 대각선 때문에 사용할 수 없는 정사각형은 16개이다. 🔍 전체 정사각형 개수 square_len = w * h 8 × 12 = 96 전체는 96개 이다. 🔥 최종 계산 이제 진짜 단순하다. answer = square_len - broken 즉, 전체 정사각형 대각선에 걸리는 정사각형 이다. 96 - 16 = 80 따라서 정답은 80 이다. 🔍 전체 코드 import math def solution(w , h): square_len = w * h gcd = math.gcd(w,h) broken = w + h - gcd answer = square_len - broken return answer 🔍 코드 한 줄씩 이해 1️⃣ 전체 정사각형 개수 square_len = w * h 👉 가로 w개 × 세로 h개 👉 전체 정사각형 개수 2️⃣ 최대공약수 구하기 gcd = math.gcd(w, h) 👉 가로와 세로를 같은 구조로 나눌 수 있는 최대 크기를 구한다. 예: gcd(8,12) = 4 이 4가 대각선의 반복되는 패턴과 연결된다. 3️⃣ 대각선에 걸리는 정사각형 broken = w + h - gcd 👉 가로/세로 방향에서 센 값을 합치고 👉 격자 교점에서 중복되는 부분을 gcd로 보정한다. 4️⃣ 사용할 수 있는 정사각형 answer = square_len - broken 👉 전체에서 대각선에 걸리는 정사각형을 뺀다. 5️⃣ 반환 return answer 👉 최종 사용할 수 있는 정사각형 개수 반환. 🧠 이번 문제에서 진짜 배운 것 이번 문제는 Python 문법 자체는 어렵지 않았다. w * h 도 어렵지 않고 math.gcd(w, h) 도 함수만 알면 된다. 진짜 어려웠던 부분은 👉 수학적인 규칙을 찾아내는 것 이었다. 특히 broken = w + h - gcd 라는 식이 처음에는 아무 의미 없이 보였다. 하지만 8 × 12 ↓ 4를 기준으로 같은 패턴 반복 ↓ gcd(8,12) = 4 ↓ 대각선이 격자 교점을 지나면서 중복 발생 ↓ w + h에서 gcd를 이용해 보정 ↓ broken = w + h - gcd 로 연결해서 이해할 수 있었다. ❗ 내가 어려웠던 부분 처음에는 broken을 어떻게 구해야 하는지 몰랐다. gcd가 최대공약수라는 것을 알게 되었지만 왜 이문제에서 필요한지 이해하기 어려웠다. w + h - gcd라는 공식이 처음에는 완전히 뜬금없었다. 하지만 8 * 12에서 4개 단위의 같은 대각선 패턴이 반복되는 것을 보고 gcd = 4와 연결할 수 있었다. 결국 이 문제는 Python 문법보다 수학적 규칙을 발견하는 게 훨씬 어려웠다. 💭 느낀 점 처음에는 "전체 크기 구하고 대각선에 걸리는 것만 빼면 되는 문제" 라고 생각했다. 이 생각은 맞았다. 문제는 대각선에 걸리는 정사각형을 어떻게 계산하느냐 였다. 처음에는 4스텝 이라는 규칙을 발견했는데, 나중에 보니까 그 4가 gcd(8, 12) 였다는 것이 연결됐다. 즉, 👉 처음에 눈으로 발견한 규칙을 👉 수학 공식으로 바꾼 문제였다. 이런 문제는 코드 자체가 어려운 게 아니라 "왜 이 숫자가 필요한지"를 찾아내는 게 핵심이라는 걸 느꼈다. 🔥 한 줄 정리 👉 전체 w × h에서 대각선에 걸리는 w + h - gcd(w,h)개의 정사각형을 빼는 수학 규칙 문제