[BOJ/백준] 26027번 : Disc District (Java)

📘 백준 26027번 : Disc District

---

문제 바로가기

🔤 문제 번역

문제

당신은 평면 세계인 Flatland의 Disc District에 살고 있으며, Nearest Convenient Plot Company(NCPC)에서 일하고 있다. 당신의 업무는 Disc District 바깥에 있으면서 Disc District와 가장 가까운 편리한(plot) 땅을 찾는 것이다.

Disc District는 평면 위에서 중심이 (0, 0)이고 반지름이 r인 원판으로 표현된다. 어떤 점이 Disc District의 바깥에 있다고 함은, 그 점과 원점 사이의 유클리드 거리가 r보다 엄격히 큰 경우를 의미한다. 평면 위의 한 점 (x, y)가 편리한 땅이 되기 위한 조건은 x와 y가 모두 정수라는 것이다.

입력

입력은 하나의 정수 r로 이루어져 있다. (1 ≤ r ≤ 10^6)

출력

Disc District 바깥에 있으면서 Disc District와의 거리가 가장 가까운 편리한 건설 위치의 좌표 (x, y)를 출력하라. 가능한 답이 여러 개라면, 그중 아무 것이나 출력해도 된다.

💡 문제 풀이

---

Disc District는 원점 (0,0)을 중심으로 반지름 r을 갖는 원판이므로, 원 바깥의 가장 가까운 정수 좌표 (x, y)는 `x² + y² > r²` 중 최소값을 찾는 문제이다.

r²에서 1씩 증가시키며 (r² + 1, r² + 2, …) 가능한 제곱합 값을 탐색한다.

각 제곱합 값에 대해 x² + y² = 해당 값이 되는 정수 x, y가 존재하는지 확인한다.

x²를 1부터 증가시키고, y²를 (제곱합 - x²)로 설정하여 두 값이 모두 완전제곱인지 검사한다.

가장 처음 발견되는 정수 좌표가 곧 Disc District 바깥에서 원과의 거리가 최소인 편리한(plot) 위치가 된다.

그런데 스페셜 저지 문제의 특성상 정답이 되는 하나의 조합만 출력하면 정답 처리된다.

정수의 제곱에 1을 더하면 정수가 어떤 값이든 (1² + 정수²)으로 표현할 수 있다.

따라서 (1, r)을 그대로 출력해도 정답이 된다.

✅ 코드 (Java)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// https://www.acmicpc.net/problem/26027
// r^2보다 1씩 증가시키며 (r^2 + 1, r^2 + 2, ...) 가능한 제곱합 값을 탐색
// 각 제곱합 값에 대해 x^2 + y^2 = 해당 값이 되는 정수 x, y가 존재하는지 확인
// x^2를 1부터 증가시키고, y^2를 (제곱합 - x^2)로 설정하여 두 값이 모두 완전제곱인지 확인
// 가장 처음 발견되는 정수 좌표를 출력
public class B26027_Disc_District_풀이1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long r = Long.parseLong(br.readLine()); // 반지름
		long r2 = r * r; // 반지름의 제곱
		long x = 0; // 정답의 x좌표
		long y = 0; // 정답의 y좌표
		Loop: while (true) { // 정답을 찾을 때까지 반복
			r2++; // 두 좌표 제곱의 합의 값을 1씩 증가하면서 찾기
			long tmpX2 = 1; // 확인할 x좌표의 제곱값
			long tmpY2 = r2 - 1; // 확인할 y좌표의 제곱값
			while (tmpX2 <= tmpY2) { 
				long tmpX = (long) Math.sqrt(tmpX2);
				long tmpY = (long) Math.sqrt(tmpY2);
				if (tmpX * tmpX + tmpY * tmpY == r2) { // 확인할 좌표가 정수가 되는지 확인
					x = tmpX;
					y = tmpY;
					break Loop;
				} else { // 안 되면 확인할 좌표를 수정
					tmpX2++;
					tmpY2--;
				}
			}
		}
		System.out.println(x + " " + y); // 출력
		br.close();
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// https://www.acmicpc.net/problem/26027
// r^2 + 1은 r^2보다 최소로 증가한 값이므로 (1, r)는 원판 바깥에서 원과의 거리가 최소인 정수 좌표 중 하나
public class B26027_Disc_District_풀이2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int r = Integer.parseInt(br.readLine());
		System.out.println(1 + " " + r);
		br.close();
	}
}

💾 제출 결과

---

보러 가기