문제링크

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

구현방법

x축과 y축으로 이루어진 서로 다른 크기의 원 2개 가 주어짐.

r1이 작은 원

r2가 r1보다 큰원

둘사이의 x y 좌표가 모두 정수인 점의 개수

-> 각 원 위의 점도 포함.

가장 큰원의 사각형

r1,r2의 크기가 100만이기때문에 2중 for문을 도는 순간 시간초과가 발생하기 때문에 O(n)으로 최대한 효율적으로 짜야한다.

가장 중요한 로직

원의 방정식

x^2 + y^2 = r^2으로

x축을 기준으로 y의값을 구한다. -> 큰원은 정수를 구하기 떄문에 내림 작은원은 올림을 진행.

4사분면중 1사분면의 값을 구한거기 때문에 마지막에 구한 점의 개수 *4를 통해서 총 개수를 도출한다.

구현 문제를 잘 못푸는 큰 문제를 발견한거같다. 구현문제를풀면서 구현력을 올리자.

원의 방정식 및 전략을 참고했습니다.

: https://judahhh.tistory.com/87

알고리즘

구현

CODE

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;


        for (int x = 1; x <= r2; x++) {
            //정수를 구하는거기때문에 내림
            long max = (int)Math.floor(Math.sqrt(1.0*r2 * r2 - 1.0*x * x));
            long min = 0;
            if (x >= r1) {
                min = 0;
            } else {
                //정수기 때문에 올림
                min = (int) Math.ceil(Math.sqrt(1.0*r1 * r1 - 1.0*x * x));
            }


            answer += max - min + 1;
        }


        // 원의 1사분면만 구한거기때문에 *4 진행
        return answer *4 ;
    }
}