문제

https://www.acmicpc.net/problem/1011

---

입력

첫째 줄에 G가 주어진다.

---

출력

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.

---

풀이

제한조건

• G는 100,000보다 작거나 같은 자연수이다.

접근방법

단순 계산 , 투 포인터
조건이 조금 명확하지 않지만, 문제 자체는 단순하다.
현재 성원이의 몸무게가 A, 이전 성원이의 몸무게를 B라고 해보자.

(A x A) - ( B x B) = G

를 만족하는 A와B를 찾으면 되는것이다.

따라서 A > B를 항상 만족해야 한다.
또한 몸무게는 0이 없다. 따라서 A=2, B=1가 탐색을 할 최소 시작점이다.
따라서 아래와 같이 두 개의 포인터를 옮겨가며 값을 구할 수 있다.

int diff = cur * cur - prev * prev;
if (diff == G) {
	cur++;
	prev++;
}
else if (diff < G) {
	cur++;
} else {
	prev++;
}

마지막으로, A와 B의 범위에 대한 설명이 없다.
그렇기때문에 어디까지 반복문을 수행하며, 투 포인터를 옮길 것인가 하는 문제가 발생한다.
하지만 조금 생각을 해보면 위에서 수식의 값을 G와 비교하며 A 또는 B의 값을 조절했는데,
수가 커지는 어느 순간, 큰 수(A)의 제곱이 너무 많이 커지기 때문에 작은 수(B)의 제곱 + G의 최댓값으로 감당할 수 없는 시점이 온다.
즉 이전값이 현재값보다 1작은데, 수식의 값이 G의 최대보다 크다면
이후의 작업은 모두 무의미한 반복이다.

if (prev + 1 == cur && diff > 100000)
	break;

따라서 위와 같은 종료조건을 설정한다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static int G;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		G = stoi(in.readLine());

		int prev = 1;
		int cur = 2;

		List<Integer> list = new ArrayList<>();
		while (true) {
			int diff = cur * cur - prev * prev;
            
            // 이제 항상 G의 최댓값보다 큰 수만 나온다면 종료
			if (prev + 1 == cur && diff > 100000)
				break;
              
			if (diff == G) {
				list.add(cur);
				cur++;
				prev++;
			}
			else if (diff < G) {
				cur++;
			} else {
				prev++;
			}
		}
		StringBuilder sb = new StringBuilder();
		if (!list.isEmpty()) // 각 원소를 StringBuilder에 추가하고 줄바꿈
			list.stream().forEach(i -> sb.append(i).append("\n"));
		else // list가 비었을 경우, 정답은 -1이다.
			sb.append("-1");
		System.out.println(sb);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}