[프로그래머스] 멀짱한 사각형

문제 설명

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

위 그림과 같이 1 x 1 크기의 격자칸으로 이루어진 직사각형의 높이와 너비가 주어졌을 때, 대각선을 포함하지 않는 격자칸의 수를 세는 문제이다. 

높이와 너비는 1억 이하의 자연수이다. 

 

풀이

대각선을 일차원 함수로 생각하면 (x,x+1) 구간에서 f(x)값을 포함하는 칸부터 y=f(x+1)값을 포함하는 칸까지가 대각선이 지나가는 격자칸의 수가 된다. 따라서 f(x+1)의 올림값에서 f(x)의 내림값을 빼면 격자칸의 개수를 구할 수 있다. 

 

f(x)값이 정수라면 x값을 기준으로 대각선이 격자칸을 지나는 패턴이 반복이 되므로 가로 길이를 x로 나눠주어 이전까지 구한 격자칸들(ans)에 배수를 해주었다. 

 

틀림

1. for문 안에서 y값을 구할 때, y = b / a * x 로 계산하게 되면 소수점에 정수를 곱하게 되어 오차가 발생한다. x 를 먼저 곱하고 a 로 나누는 코드로 변경했다. 
2. 위 코드로 변경하니 테케 하나에서 시간초과가 떴다. 높이와 너비 중에 작은 값을 a로 설정하니 해결되었다

코드 

import math


def solution(w, h):
    ans = 0

    # 높이와 너비 중 작은 값을 a로 설정
    if w <= h:
        a = w
        b = h
    else:
        a = h
        b = w

    # `y=(b/a)* x` 일차원 함수에서 현재 y의 올림값과 이전 y의 내림값 차이를 구함 
    bottom = 0
    for x in range(1, a + 1):
        y = b * x / a
        ans += math.ceil(y) - math.floor(bottom)

        if y == int(y):
            ans *= a // x
            break

        bottom = y

    return w * h - ans