문제 링크

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

문제 설명

• W * H 크기의 직사각형 종이가 주어짐
• 대각선으로 잘랐을 때 사용 가능한 정사각형의 개수 리턴

틀린 풀이

• 최대한 효율적으로 풀어보려 했는데 실패
• 그래프 탐색 방식
• 예제 그림대로 w < h라고 가정
• (0, 0) 부터 (h // gcd, w // gcd) 까지 탐색
• 조건문을 넣어줌
  
• 조건문에 따라 오른쪽 또는 아래로 이동
  

틀린 코드

from math import gcd

def solution(w,h):
    if w > h:
        w, h = h, w
    g = gcd(w, h)
    nw = w // g
    nh = h // g
    a = nw / nh
    count = 0
    y, x = 0, 0
    while x < nw and y < nh:
        if (x <= y * a < x + 1) and (x < (y+1) * a <= x + 1):
            count += 1
            y += 1
        elif x <= y * a < x + 1:
            count += 1
            x += 1
        elif x < (y+1) * a <= x + 1:
            count += 1
            y += 1
    return w * h - count * g

맞은 풀이

• gcd 로 자른 것까지는 맞음
• gcd 로 자르게 되면 w, h 가 서로소이기 때문에
• 잘린 부분이 아래로, 또는 옆으로 연결되게 된다
• 그래서 잘린 부분의 개수는
• 첫번째 좌표에서 마지막 좌표까지의 최단거리 + 1 과 같다
• 최단거리 = (오른쪽으로 w-1번 이동) + (아래로 h-1번 이동)

맞은 코드

from math import gcd

def solution(w,h):
    g = gcd(w, h)
    nw = w // g
    nh = h // g
    return w * h - (nw + nh - 1) * g