문제
https://school.programmers.co.kr/learn/courses/30/lessons/62048
풀이과정
이 문제는 아이디어 + 시간초과 해결이 포인트인 것 같다.
문제를 이해하는 데 시간이 조금 걸렸고, 풀이 아이디어가 생각나지 않았다.
규칙을 찾아보려 했지만 1시간이 넘도록 생각이 나지 않아 다른 사람이 적어둔 힌트를 보았다.
힌트는 기울기를 이용하는 것.
y = 1.5x 인 상황이라면, x=1일 때 y=1.5가 된다.
이때, 대각선 아래에 위치하는 멀쩡한 사각형은 x=1, y=1 인거 1개이다.
x=2일때는 y=3이다. 이때는 (2,1), (2,2), (2,3) 이렇게 멀쩡한 사각형이 3개가 된다.
이런 방식으로 x=1 ~ 7 까지 생각해보면
1 + 3 + 4 + 6+ 7 + 9 + 10 이 되어서 대각선 아래쪽에 총 40개의 멀쩡한 사각형이 존재할 수 있고 대각선 위로는 대칭이므로 총 80개가 존재하는 것을 구할 수 있다.
이 로직으로 코드를 파이썬으로 작성하면 시간초과가 나온다.
w, h가 1억까지 커질 수 있기 때문이다.
따라서, 최대공약수로 나누어주고 반복되는 부분만큼 곱해주는 방식으로 작성하여 효율성을 증가시켰다.
이렇게 해도 11번 테스트케이스는 시간초과가 해결되지 않았다.
이 부분은 'w, h 중 더 작은 것을 기준으로 반복문을 돌린다.'가 포인트였다!
여러 힌트 덕분에 풀이할 수 있었던 문제라서 개인적으로 아쉬움이 남는다.
체화시켜서 다음에는 스스로 생각해내기...
코드
import math
def solution(w,h):
gcd = math.gcd(w, h)
sub_w = int(w / gcd)
sub_h = int(h / gcd)
answer = 0
if sub_w <= sub_h:
for i in range(1, sub_w):
answer += int(sub_h * i / sub_w)
answer *= 2
answer += ((w - sub_w) * sub_h)
else:
for i in range(1, sub_h):
answer += int(sub_w * i / sub_h)
answer *= 2
answer += ((h - sub_h) * sub_w)
return answer * gcd다른 사람의 풀이
def solution(w,h):
from math import gcd
k = gcd(w,h)
w2 = w/k
h2 = h/k
return int(w*h-(w2+h2-1)*k)대각선이 지나가는 사각형의 수는 w+h-gcd 라는 규칙이 있는 듯 하다. (신기)
