프로그래머스 Summer/Winter Coding(2019) : 멀쩡한 사각형 - python3 풀이

문제 보러 가기👈 클릭!

💡 풀이

✔ 문제 파악

• 가로,세로 길이가 w,h인 직사각형이 주어졌을 때, 대각선을 긋고 가로,세로 길이가 1인 멀쩡한 정사각형의 개수를 return.

✔ 풀이 방법

• 직사각형에서 대각선을 그으면 똑같은 2개의 직각삼각형이 생김 -> 하나의 직각삼각형에서 멀쩡한 정사각형의 개수를 구하고, 그것의 2배를 return.

• 위의 그림과 같이 대각선을 일차함수로 생각-> x=1,2,3,...w일 때, 멀쩡한 삼각형의 개수 = x=1,2,3,...w일 때, y값 보다 이하인 정수들 중 최대값

• 문제점

def solution(w,h):
    answer = 0
    
    for x in range(1, w+1):
        y = (-h/w)*x + h
        answer += int(y)
        
    return answer*2

다음과 같이 풀면 테스트케이스 11,12에서 시간초과가 발생.
-> 가로 세로 길이 둘 중 하나라도 1인경우 : 멀쩡한 삼각형 개수는 0
가로길이와 세로길이가 같은 경우 : 멀쩡한 삼각형 개수는 원래 전체 사각형 개수 - 가로길이(=세로길이)

💡 전체 소스 코드

def solution(w,h):
    answer = 0
    
    if w == 1 or h ==1 :
        return 0
    elif w == h:
        return w * h - h
    else:
        for x in range(1, w+1):
            y = (-h/w)*x + h  #일차함수 식(기울기=-h/w, y절편=h)
            answer += int(y)
        return answer*2