점 찍기

링크텍스트

문제 설명

1. 원점(0,0)으로 부터 x=x곱하기k(x=0,1,2,3,4,,,,), y=y곱하기k(y=0,1,2,3,4,,,,,)로 늘어날 때, 원점에서 그 점까지의 거리가 d이하인 점들의 갯수 반환

시행착오 및 문제 풀이

처음에 풀었던 방식

오답 풀이

1. 이중 for문을 돌며 x와 y가 k씩 늘어나는 경우를 계산한다. 이때 그 거리가 d를 넘어서면 break해주고 아니라면 answer++ 해준다.

오답 코드

import java.util.*;
class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        int x=0;
        int y=0;
       
        for(int i=0; i<d*d; i++) {
            for(int j=0; j<d*d; j++) {
                
                x = i*k;
                y = j*k;
                
                //d를 넘어서면 패스
                if(Math.sqrt(x*x+y*y) > d) {
                    break;
                }
                answer++;
            }
        }
        return answer;
    }
}

그저 빵점;
그래서 조금 더 보완해줬다.
x와 y를 따로 계산하지 않고 for문 안에서 k씩 늘어나도록

import java.util.*;
class Solution {
    public long solution(int k, int d) {
        long answer = 0;
       
        for(int i=0; i<=d; i+=k) {
            for(int j=0; j<=d; j+=k) {
                
                //d를 넘어서면 패스
                if(Math.sqrt(i*i+j*j) > d) {
                    break;
                }
                answer++;
            }
        }
        return answer;
    }
}

오답!
사실 제한사항의 k와 d가 백만까지 일 때부터 이중 for문은 틀렸을 거라 확신했다ㅜ

정답 풀이

1. i^2 + j^2 <= d^2 -> j^2 <= d^2-i^2 원리를 이용한다

2. 효율성을 위해 총 거리는 for문 밖에서 계산해준다. 루트를 없앤 총 거리는 dis

3. for문 속의 i를 임의로 x 고정 값이라고 생각한다.

4. now_dis는 i를 고정해놨을 때 갈 수 있는 거리를 나타낸다.

5. 이 거리에서 k칸씩 갈 수 있는 거리는 now_dis/k이다. 이때, +1은 0을 포함하기 때문이다.
   예제를 통해 알아보자면
   5-1. i=x=0, d=4) 현재 내가 갈 수 있는 거리는 4이다. k씩 늘어나므로 y좌표가 될 수 있는 값은 0,2,4이다. 4(now_dis)/2 + 1 = 3개이다.
   -> (0,0) (0,2) (0,4)

   5-2. i=x=2) 현재 내가 갈 수 있는 거리는 2루트3이다. k씩 늘어나므로 y좌표가 될 수 있는 값은 0,2이다. 2/2 + 1 = 2개이다.
   -> (2,0) (2,2)

   5-3. i=x=4) 현재 내가 갈 수 있는 거리는 0이다. k씩 늘어나므로 y좌표가 될 수 있는 값은 0이다. 0/2 + 1 = 1개이다.
   -> (4,0)

6. answer에 갯수를 모두 더하여 반환한다.

정답 코드

//i^2 + j^2 <= d^2 -> j^2 <= d^2-i^2
import java.util.*;
class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        
        //거리
        long dis = (long)d*d;
        
        for(int i=0; i<=d; i+=k) {
            //i를 고정해놨을 때 갈 수 있는 거리
            long now_dis = (long)Math.sqrt(dis - (long)i*i);
            
            answer += (now_dis/k)+1;
        }
        return answer;
    }
}

정답!
사실 푸는 방법이 생각 안나서 저번에 풀었던 풀이 방식을 참고했다.
어차피 d를 넘어가는 경우는 카운트하지 않으므로 애초에 거리(d)에서 x의 값을 빼서 그 안에서만 y의 값을 구한다. 그럼 for문 1개면 된다. 이런 생각을 못했다...

그리고 (현재 갈 수 있는 거리/k) +1 이건 진짜 신박했다
약간 이러한 수학적 요소? 이런 걸 잘해야 할텐데... 떼잉
코드는 어렵진 않았지만 조금 창의성이 필요한 문제였던 것 같다~