로그인
  1. 코딩테스트 연습
  2. Summer/Winter Coding(2019)
  3. 멀쩡한 사각형
  4. 질문목록
  5. 개수세는 원리(최적화x)
강의로 돌아가기
김동규
답변 작성

개수세는 원리(최적화x)

일단 w와h를 최소공배수로 나눠줍니다

  • 이렇게 하면 꼭지점과 꼭지점이 만나는 최소공배수의 개수를 갖는 그룹이 나옵니다 ex) 812 사각형 기준 23의 패턴이 4번 반복 사각형을 w>h인 형태로 돌려서 생각합니다.
  • 이 경우 기울기가 항상 1보다 작습니다.
  • 기본적으로는 w가 1 증가할 때마다 1개의 사각형만 잘리게 됩니다.
  • 추가로 대각선이 y는 정수인 선과 만날 때만 위아래로 2개의 사각형이 잘립니다.
  • w>h인 h를 기준으로 사각형 내부에는 y가 정수인 선이 h-1개가 생기고 해당 선과 접하는 사각형들이 2개씩 잘립니다. 결과로 gcd로 나눠진 그룹에 대하여 잘리는 사각형의 개수는 w'+h'-1이라는 공식이 나옵니다. 각 그룹에 대해 나오는 cut의 개수를 알았으니 총 사각형 개수에서 cut*gcd(=그룹의 개수)를 빼줍니다.
작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10

from math import gcd
import math
def solution(w,h):

    cnt = gcd(w,h)
    total = w*h
    w//=cnt
    h//=cnt
    cut = max(w,h)+min(w,h)-1
    return total - cut*cnt
  • 코코종

    좋은 글 감사합니다! 한가지만 말씀드리면 최소공배수가 아니라 최대공약수인 것 같습니다! 다른분들께서 이해하실 때 도움이 조금이나마 되고자 댓글 남깁니다!(최대공배수라고 써서 수정했습니다)

    코코종―2023.05.12 19:08
  • jwun95

    좋은 글 감사합니다! 한가지만 말씀드리면 최소공배수도 최대공배수도 아닌 최대공약수인 것 같습니다! 다른분들께서 이해하실 때 도움이 조금이나마 되고자 댓글 남깁니다!

    jwun95―2023.07.05 18:01
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다.