[프로그래머스] 점 찍기

문제

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

프로그래머스

문제 분석

[제한사항]

• 1 ≤ k ≤ 1,000,000
• 1 ≤ d ≤ 1,000,000

 

문제를 풀기 쉽게 요약하면 위에 그림처럼 k=2, d=6 으로 주어졌을 때 파란점의 개수를 구해야 하는 문제이다.

 

문제 접근

주어진 k 와 d 모두 최대 10^6 까지 가능하다.

그렇기 때문에 최악의 경우 k=1, d=10^6 일 경우에는 가능한 모든 좌표들을 하나하나 확인하며 거리 비교를 할 수 없다 (시간 초과)

 

그렇다면 공식을 세워서 문제를 풀어야 한다.

 

x = 0, y= 4 일 때, 해당 y축 (x=0) 에 가능한 좌표는 4 / 2 + 1 개이다.

즉, (x, 가능한 y 최대 값) 일 때, 해당 y 축에 가능한 좌표는 y 최대값 / k + 1 이다.

 

y의 최대값만 구하면 가능한 x 값들을 순회하면 모든 가능한 좌표를 구할 수 있다.

 

주의할 점은 계산 하면서 int 자료형의 크기를 넘어갈 수 있기 때문에 중간 계산도 long 자료형으로 바꾸어서 계산해주어야 한다.

코드

import java.util.*;

class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        long y = d;
        for(long x=0; x<=d; x+=k){
            while(x * x + y * y > (long)d * d){
                y -= 1;
            }
            answer += y/k + 1;
        }
        return answer;
    }
}