[알고리즘] 프로그래머스 - 점찍기 (Java)

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

프로그래머스

 

1. 실패 코드 (시간초과) - DFS 풀이

package Programmers;

import java.util.ArrayList;
import java.util.List;

public class 점찍기 {

    static int[] pm = new int[2];
    static int answer = 0;

    public static void main(String[] args){
        점찍기 T = new 점찍기();
        int k = 1;
        int d = 5; //원점과 거리
        T.solution(k, d);
    }

    public long solution(int k, int d) {
        List<Integer> tempArr = new ArrayList<>();
        for (int i = 0; i <= d; i++) {
            if(k * i > d) break;
            tempArr.add(k * i);
        }
        int[] myArr = new int[tempArr.size()];
        for (int i = 0; i < tempArr.size(); i++) {
            myArr[i] = tempArr.get(i);
        }
        //myArr을 만든다.
        dfs(0, myArr, d);
        return answer;
    }
    public void dfs(int L, int[] myArr, int d){
        if(L == 2){
            if(calc(pm, d)){
                answer++;
                return;
            }else{
                return;
            }
        }
        for (int i = 0; i < myArr.length; i++) {
            pm[L] = myArr[i];
            dfs(L+1, myArr, d);
        }
    }
    public boolean calc(int[] pm, int d){
        int x = pm[0];
        int y = pm[1];
        double a = Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
        if(a <= d) return true;
        return false;
    }

}

 

12/16 개 성공 케이스다 시간초과 남.     

  1. 가능한 좌표 케이스 배열로 만들어서 좌표를 pm에 다가 넣고 calc에다가 보낸다.

  2. calc 에서 거리가 맞는지 확인하고 true false 로 반환. 

 

   ======== 시간초과남 =============

 

 

 

2. 코드수정 

package Programmers;

public class 점찍기 {
    public static void main(String[] args){
        점찍기 T = new 점찍기();
        int k = 2;
        int d = 4; //원점과 거리
        T.solution(k, d);
    }

    public long solution(int k, int d) {
        long answer = 0;
        for(int i = 0; i <= d; i += k)
        {
            long dd = (long) d * d;
            long ii = (long) i * i;
            int top = (int) Math.sqrt(dd - ii);
            answer += (top / k) + 1;
        }
        return answer;
    }
}

1. 원의방정식 a^2 + b^2 = c^2 활용해서 풀면된다

2. 원의방정식에 따라서 x좌표(i)와 거리값을 알면 y값(top)이 산출된다.

3. x좌표(i) 일때 나올수 있는 최대 정수 y 에다가 k배수만큼 나눠주면 찍을수 있는 좌표가 나온다. 

ex). i = 2 일때 원의방정식에따라서 top(y) = 3.xxxxx 이고 최대지점은 (2, 3.xxxxx) 이므로 y가 3.xxxx 밑에있는 2의 배수지점을 모두 찾아 주면 된다.

 

+1 은 0 포함 해야하니까

 

 

※ 제한조건 보니 DFS로는 안풀릴거라 예상은했지만 수학적사고방식으로 푸는 학습이 더 필요할것같다.