Question

개수 세는법 (아랫분 의견과 결과는 같지만 조금 더 이해하기 쉽게 설명!) - 정답 스포 주의!!

먼저 간단한 w * h 를 그려가며 실제로 대각선을 그어보거나 예시를 보니 대각선을 지나는 부분에 패턴이 반복되는건 확인이 가능할 겁니다! 이때 gcd(최대공약수)를 이용해 몇개나 반복되는지 찾으면 됩니다 (8 12 의 경우 gcd는 4가 되고 이만큼 반복됩니다.)

자, 이제 작은 하나의 패턴을 살펴보며 몇개나 대각선에 닿지 않는지를 세어보면 흰색으로 된 부분을 뺀 위 아래 남은 부분을 합치게 되면 (테트리스처럼요!) w-1 * h-1 의 직사각형이 되는 것을 확인할 수 있습니다! 즉, 지워진 영역의 크기를 알 수 있다는 것이죠!

이때 작은 패턴의 가로, 세로를 ww, hh 라고 하면 이 중 흰색이 아닌 부분은 (ww-1)(hh-1) 이 되므로 여기서 흰 부분(잘린 부분)의 크기를 알 수 있습니다. 흰 부분의 크기는 결국 wwhh - (ww-1)*(hh-1) 을 하게되면 결국 h + w -1이 됩니다!
마지막에 전체에서 이 흰부분 * gcd 한만큼을 빼주시면 됩니다~!

작성중인 코드―solution.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from math import gcd
def solution(w,h):
    answer = 1

    w, h = max(w,h), min(w, h) # 편의상 가로가 더 길게

    g = gcd(w,h) # 최대 공약수 -> (패턴 반복수)

    ww = w // g
    hh = h // g # 간소화 된 w, h
    # print(ww, hh, g)

    # ww * hh 에서 대각선을 지나지 않는 크기는 (ww-1) * (hh-1)
    # cut: 패턴의 한부분 ww * hh 에서 잘리지 않는 부분을 뺀 것
    # 실제로는 w + h -1 과 같다.
    cut = ( (ww * hh) - (ww - 1) * (hh - 1) )


    answer = w * h - cut * g

    return answer

코코종

2023.5.12 19:43

개수 세는법 (아랫분 의견과 결과는 같지만 조금 더 이해하기 쉽게 설명!) - 정답 스포 주의!!

작성중인 코드―solution.py

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.

코코종

2023.5.12 19:43

개수 세는법 (아랫분 의견과 결과는 같지만 조금 더 이해하기 쉽게 설명!) - 정답 스포 주의!!

작성중인 코드―solution.py

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.

코코종