점 찍기

문제 설명

원점으로 부터 (a*k, b*k)의 위치에 점을 찍는데, 만일 원점으로부터 거리가 d를 넘는 위치이면 점을 찍지 않는다. 찍을 수 있는 점의 수를 구하는 문제이다.

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

프로그래머스

문제 풀이

첫 번째 접근

k와 d의 범위를 보는 순간 2차원 반복문을 쓰면 시간 초과가 날 것임을 직감했다.

그래도 혹시 몰라서 2차원 반복문으로 풀어봤는데, 역시나 시간 초과

        while(true){
            int xK = x*k;
            if(xK > d){
                break;
            }
            while(true){
                int yK = y*k;
                if(yK > d){
                    break;
                }
                //Pair는 따로 만들어준 클래스
                Pair end = new Pair(xK, yK);
                //System.out.println(xK + " " + yK);
                //cal은 따로 만들어준 메소드
                if(cal(start, end, d)){
                    answer += 1;
                }
                y += 1;
            }
            y = 0;
            x += 1;
        }

두 번째 접근

사실 이 문제에서 포인트는 형 변환이다.

문제 자체는 x^2 + y^2 <= d^2인 원 내에서 점을 찍는 것인데, 여기서 계산을 할 때 형변환을 꼼꼼하게 해줘야 한다.

 

x를 기준으로 증가한다고 했을 때, y^2의 범위는 0과 d^2 - x^2 사이에 있다고 할 수 있다. 위의 계산으로 y의 최댓값을 구해준 다음 k로 나누고 1을 더해서 가능한 좌표의 수를 구해주면 된다.

 

중요한 점은 java에서 제곱을 해주려면 Math.pow()를 사용해야 하는데, Math.pow는 double을 반환한다는 점이다. Math.sqrt안에는 double이 들어가도 상관 없지만 k로 나눴을 때 나눠떨어져야 하니까 sqrt해주고 난 값을 int로 형변환 해줘야 한다.

answer += ((int)Math.sqrt((Math.pow(d, 2) - Math.pow(a*k, 2))) / k) + 1;

코드

java

class Solution {
    public long solution(int k, int d) {
        long answer = 0;

        for(int a=0; a*k<=d; a++){
            answer += ((int)Math.sqrt((Math.pow(d, 2) - Math.pow(a*k, 2))) / k) + 1;
        }
        return answer;
    }
}

import math

def solution(k, d):
    answer = 0
    a = 0
    
    while True:
        if a*k > d:
            break
        answer += (int(math.sqrt(math.pow(d, 2) - math.pow(a*k, 2)))//k)+1
        a += 1
        
    return answer