백준 1484 : 다이어트

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

1484번: 다이어트

[ 문제풀이 ]

수학적으로 접근하면 쉽게 해결할 수 있는 문제이다.현재 몸무게를 x, 기억하고 있던 몸무게를 y로 둔다면 다음과 같이 표현할 수 있다.

G = x^2 - y^2

이를 풀어보면 다음과 같으며 결국 (x+y)와 (x-y)는 G의 약수여야 한다는 것을 알 수 있다.

G = (x+y)(x-y)

따라서 루트 G부터 1까지 차례대로 탐색해주면서 G의 약수를 찾아주면 된다.

주의해야 할 점은 우리가 구하고자 하는 값은 x이기 때문에 (x+y)와 (x-y)를 +하여 2x를 구한 후 2로 나눌 것이다. 이때 몸무게는 자연수여야 한다는 조건이 있기 때문에 더해준 값이 짝수여야 한다.

또한, 몸무게는 자연수이기 때문에 0이 될 수 없다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			int G = Integer.parseInt(br.readLine());
			boolean find = false;
			//G = x^2 - y^2 = (x + y)(x - y)
			//x + y = G/k, x - y = k
			//x = (G/k + k)/2, y = (G/k - k)/2
			for (int k = (int) Math.sqrt(G); k >= 1; --k) {
				if (G % k != 0) continue;
				int v = G / k;
				if ((v + k) % 2 != 0 || (v - k) / 2 == 0) continue;
				find = true;
				bw.write((v + k) / 2 + "\n");
			}	
			if (!find) bw.write("-1\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}