[Programmers] 두 원 사이의 정수 쌍 / ⭕

프로그래머스

 

1. 제출코드 (1시간 11분 24초)

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        // X축을 기준
        for(int i = 1; i <= r2; i++) {
        	// Y의 최댓값
            int max = (int) Math.floor(Math.sqrt(Math.pow(r2, 2) - Math.pow(i, 2)));
            // Y의 최솟값
            int min = 0;
            if(i < r1) {
                min = (int) Math.ceil(Math.sqrt(Math.pow(r1, 2) - Math.pow(i, 2)));
            }
            
            answer += max - min + 1;
        }
        
        return answer * 4;
    }
}

 

2. 실패코드

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        int[] memo = new int[1000001];
        memo[0] = 0;
        memo[1] = 0;
        memo[2] = 1;
        memo[3] = 4;

        for(int i=4; i <= 1000000; i++) {
            memo[i] = memo[i - 1] + (memo[i - 1] - memo[i - 2] + memo[i - 2] - memo[i - 3]);
        }
        answer = (memo[r2] * 4) - (memo[r1] * 4) + 8;
        return answer;
    }
}

 

3. 유의할 점

• r1과 r2의 범위가 1 <= r1 < r2 <= 1,000,000 이기 때문에 for문을 2번 돌리는 것은 시간초과가 날 것 같았다.
• 그래서 memoization 같이 규칙이 보는 거 같아 DP로 시도를 해봤는데 이것도 되지 않았다.
• 다시, 돌아가서 1사분면의 점들을 구하고 * 4를 해주는 방법을 시도해봤다
• 피타고라스 정의를 이용해서 각 X축마다의 Y값 정수 최대값과 최솟값을 구했다.
• 최댓값 - 최솟값 + 1을 통해 하나의 X축의 점의 개수를 구하고 for문을 돌려 각 X축마다의 점의 개수를 구했다. 그리고 *4를 통해 정답을 구할 수 있었다.