Question

테케40점 맞은사람들은 참고.. (Java) (풀이 O)

아마 저처럼 풀으셧으면 40점을 맞앗을겁니다..

일단 x=0 ,y =0 좌표평면 제외하고

원 2개의 겹치지않는 영역인 1사분면만 구한뒤, 4를곱합니다.

이건 y제곱 = r제곱 - x제곱으로 r1 r2 각각 구한뒤 뺏습니다.

그 후, 좌표평면 x=0 ,y=0 은 무조건 2개니깐 +8개 이렇게 했더니 40점이 나오더군요.

곰곰히 생각해보니 이런 케이스는 놓칠거 같았습니다.

5² = 4²⁺ 3² 처럼, 반지름이 좌표평면 말고도 1사분면 좌표내부 에서도 딱 맞는 케이스,,

이 케이스 잡아줬더니 풀렸습니다.

작성중인 코드―Solution.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;
class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;


        long r1x = (long)Math.pow(r1,2);
        long r2x = (long)Math.pow(r2,2);

        //y^2= r^2-x^2

        long y1sum=0;
        long y2sum=0;
        long side =0;

        for(long i=0;i<=r2;i++){


           long y2 = (long)Math.sqrt(r2x-(long)Math.pow(i,2));

           long y1 = (long)Math.sqrt(r1x-(long)Math.pow(i,2));


           if(Math.sqrt((r1x-Math.pow(i,2)))%1==0){
               side++;
           }

            answer+=(y2-y1)*4;
        }

        answer+=side*4-4;



        return answer;
    }
}

Math.sqrt(r2x-(long)Math.pow(i,2)) 이 식이 왜 이렇게 이루어 지는지 알려주실 수 있으실까요?? ㅠㅠ 도저히 이해가 안가네요 ㅠ 구글링해도 관련 알고리즘 안나오고 ㅠ

ajw1587@gmail.com―2023.04.14 23:04
우선 저희는 r 반지름을 압니다. 그리고 X좌표기준으로 탐색을시작하면, y^2= r^2 -x^2 => 피타고라스의 방정식을 변형 할수있습니다. Math.sqrt()를 넣어주면 y값이 나오죠, 이러면 X가 0일때 y가 가능한 갯수, 1일때 y가 가능한갯수... 등등 가능한 y갯수가 저절로 구해집니다.

김태홍―2023.04.15 00:06
아하... 피타고라스 이용한 거였군요!! 괜히 다른 알고리즘이 있나 엄청 찾아봤네요! 감사합니다 ㅎㅎ

ajw1587@gmail.com―2023.04.15 15:20
혹시 31행 -4를 왜 하셨는지 알려주실 수 있을까요ㅠㅠ?? 다른 로직은 이해되는데 -4는 왜 하는지 이해가 안가서요 ㅠㅠ

전세연―2023.04.16 16:20
31행에 -4는 그겁니다. 1사분면 탐색하는데 y=0 테두리부터 ~ x=0 테두리까지 탐색하는데, 이걸 *4하면 y=0 , x=0 테두리를 2번씩탐색하게되요. 여기서 -1씩 4번빼줘야해서 -4를 한겁니다.

김태홍―2023.04.16 17:14

김태홍

2023.4.14 00:15

테케40점 맞은사람들은 참고.. (Java) (풀이 O)

작성중인 코드―Solution.java

ajw1587@gmail.com―2023.04.14 23:04

김태홍―2023.04.15 00:06

ajw1587@gmail.com―2023.04.15 15:20

전세연―2023.04.16 16:20

김태홍―2023.04.16 17:14

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.