[SWEA] 16910번 : 원 안의 점

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYcllbDqUVgDFASR&categoryId=AYcllbDqUVgDFASR&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=3

SW Expert Academy

 

문제

N이 주어질 때, 원점을 중심으로 반지름이 N인 원 안에 포함되는 격자점(x,y 좌표가 모두 정수인 점)의 개수를 구하는 프로그램을 작성하라.

다시 말하자면, x^2+y^2<=N^2인 격자점의 개수를 구하는 프로그램을 작성하라.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1<=N<=200)이 주어진다.

 

출력

각 테스트 케이스마다 반지름이 N인 원 안에 포함되는 격자점의 개수를 출력한다.

 

---

소스코드

import java.io.*;

class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int n2 = n * n;
            int x = 0, y;

            // 0이 포함된 경우, 포함되지 않은 경우
            int result1 = 0;
            int result2 = 0;
            while(x*x <= n2) {
                y = 0;
                while(true) {
                    if (x * x + y * y <= n2) {
                        if (x == 0 || y == 0) result1 += 1;
                        else result2 += 1;
                    } else {
                        break;
                    }
                    y += 1;
                }
                x += 1;
            }

            // 양양 음음 (0, 1) (0, -1)
            result1 = (result1 * 2) - 1;
            // 양양 음음 양음 음양 (1, 1) (-1, -1) (1, -1) (-1, 1)
            result2 = (result2 * 4);
            sb.append("#" + (i + 1) + " " + (result1 + result2) + "\n");
        }

        System.out.println(sb);
    }
}

 

해결 방법

1. x 혹은 y 좌표 중 0이 포함된 경우와 포함되지 않은 경우를 나눠서 x^2+y^2 <= N^2인 격자점을 구한다.
2. 0이 포함되어 있다면 나올 수 있는 경우는 (양수, 양수), (음수, 음수) 조합이다. 고로 (result1 * 2) - 1의 식이 성립한다. -1을 하는 이유는 (0, 0)에 경우 2번 들어가면 안 되기 때문이다.
3. 0이 포함되어 있지 않다면 나올 수 있는 경우는 (양수, 양수), (음수, 음수), (양수, 음수), (음수, 양수) 조합이다. 고로 (result2 * 4)의 식이 성립한다.