[pro] 프로그래머스 level2 140107 점 찍기 (Java) - 시뮬레이션

[문제]

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

프로그래머스

 

[풀이]

d의 범위가 <=1,000,000 이므로 이중 for 문을 돌리면 시간초과가 발생할 것이다. 따라서 한번의 for문으로 O(n)으로 해결 하도록 했다.

0~d까지의 x값에 대하여 (0,0)에서의 거리가 d가 되게 하는 최대 y값을 구할 수 있다. 최대 y 이내의 값들에 대해 정답에 포함될 수 있고, *k씩 커질 수 있으므로 가능한 y의 개수는 y/k + 1 이 된다.

주의할 점은 d*d, x*x 가 int의 범위를 초과하므로 long으로 캐스트 후에 sqrt 함수를 사용할 수 있도록 해야 한다.

 

[코드]

 

import java.util.*;
class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        //점이 총 몇 개 찍히는지 return 
        
        for(int x=0; x<=d; x+=k){
            int y = (int)Math.sqrt((long)d*d - (long)x*x); //y의 최댓값
            answer += (y/k+1);
        }
        
        return answer;
    }
}