[프로그래머스] 두 원 사이의 정수 (Python)

문제 링크

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

프로그래머스

소스 코드

import math

def solution(r1, r2):
    answer = 0
    for x in range(1,r2+1):
        max_r1 = 0 if x > r1 else (r1**2-x**2) ** 0.5 # r1 이상 y
        max_r2 = (r2**2-x**2) ** 0.5 # r2 이하 y
        
        answer += math.floor(max_r2) - math.ceil(max_r1) + 1 # 최소 1개
        
    return answer * 4

해설

• 수학, 구현

처음엔 r이 증가함에 따라 특정 규칙이 발생하는 DP 유형인 줄 알았습니다.

그런데 DP로 접근하지 너무 일관된 규칙으로만 파악이 되고(원을 제대로 그려볼 수가 없으니..) 특정 케이스만 만족시킬 수 있는 답이 나왔습니다.

 

그래서 정확한 규칙을 수식으로 구하여 풀이할 수 있도록 조정했습니다.

마지막 결과에서 4를 곱하여 return하는 것을 보면 알 수 있는 것처럼 한 사분면에서의 값만 구하는 로직입니다.

 

반지름이 1부터 r2까지인 케이스들을 조사합니다(for문)

이때 변수명은 x인데 원을 구할 때 x^2 + y^2 = r^2 임을 이용하여 y 값을 구합니다.

이렇게 하면 y가 정수인 케이스가 곧 x, y가 정수인 케이스가 되기 때문입니다.

(y^2 = r^2 - x^2)

 

따라서 x가 r1 미만인 값들은 고려할 필요가 없고, r1 이상 r2 이하인 경우만 생각합니다.

r2에 대해서는 소수점을 제거해줘야 '이하'를 만족할 수 있고, r1에 대해서는 올림을 해줘야 '이상'을 만족할 수 있습니다.

예를 들어 r1 = 1.5, r2 = 3.5 라고 가정해보면, r1 = 2, r2 = 3 이 되어야 우리가 그려낼 원 사이의 값들을 구할 수 있게 되죠.