[ BOJ ][JAVA][1484] 다이어트

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

1484번: 다이어트

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3273	1239	976	35.362%

문제

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

15

예제 출력 1

4
8

접근

수식을 써보니 (A + B)(A - B)의 형태가 만들어지는 것을 확인했고 그대로 구현했다.

코드

/**
 * BOJ 1484 다이어트
 * 수학
 */
import java.io.*;
import java.util.*;

public class p1484 {
    static int g;
    static List<Integer> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        g = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        // g: 15
        // 15킬로그램이나 쪘어!!!
        // 현재몸무게 cur^2 - 기억^2 = 15
        // (a + b)(a - b) = 15
        // 4 + 1 * 4 - 1
        // 8 + 7 * 8 - 7
        for (int i = 1; i <= g; i++) {
            // 현재 몸무게 테스트
            if (g % i != 0) continue;

            // 더해서 i가 만들어지는 경우를 본다
            for (int j = 1; j <= i / 2; j++) {
                int a = j;
                int b = i - j;

                int big = Math.max(a, b);
                int small = Math.min(a, b);
                if ((big + small) * (big - small) == g) {
                    list.add(big);
                }
            }
        }
        if (list.size() == 0) {
            System.out.println(-1);
        } else {
            Collections.sort(list);
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
        }
    }
}