[Baekjoon] 1484번: 다이어트

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

1484번: 다이어트

문제 설명

입력된 G값은 현재 몸무게의 제곱에서 기억하고 있던 몸무게의 제곱을 뺀 값이다. 현재 몸무게로 가능한 모든 수를 출력해야 한다.

풀이 방법

투 포인터를 활용해 간단하고 효율적으로 해결할 수 있다.

모든 수를 출력하는 것 외에 다른 제한이 따로 없어서 당황할 수 있는데 규칙을 찾으면 반복의 종료 조건을 찾을 수 있다.

예제 입력으로 흐름을 따라가보자.

먼저 기억하고 있던 몸무게를 left, 현재 몸무게를 right라고 하자. 이는 각각 1과 2를 가리키고 있다.

1. 각 수를 제곱하여 뺀 값은 4 - 1 = 3이다. 3은 현재 맞춰야 하는 G인 15보다 작다. 따라서 right를 1만큼 증가시킨다.
2. 다시 각 수를 제곱하여 빼면 9 - 1 = 8이다. 이 결과 또한 G보다 작으므로 right를 1만큼 증가시킨다.
3. 다시 각 수를 제곱하여 빼면 16 - 1 = 15이다. 이제 G와 같아졌다. 현재 몸무게 값인 right를 저장한다. 그리고 left와 right를 함께 1만큼 증가시킨다. 왜냐하면 left만 증가시켜도 어차피 G가 나오지 않기 때문이다.
4. 그럼 현재 left = 2, right = 5이다. 25 - 4 = 21이다. G보다 결과값이 크므로 left를 1만큼 증가시킨다.
5. 다시 계산하면 25 - 9 = 16이다. 아직도 G보다 크므로 left를 1만큼 증가시킨다.
6. 이런 식으로 계속 계산해 나가다 left가 right와 같아지면 반복을 종료한다.

left와 right가 같아진다는 의미는 더 이상 right와 left를 증가시켜도 G를 구할 수 없다는 것이다. 8을 넘어가서는 G를 구할 수 있는 경우가 없을까? 없다. 9의 제곱인 81과 9에 가장 가까운 8의 제곱인 64의 차는 17이다. 10의 제곱인 100과 10과 가장 가까운 9의 제곱인 81의 차는 19이다. 규칙이 보이는가? 가장 가까운 두 수의 제곱의 차가 G라면 그 이후는 더 이상 G를 구할 수 없다는 것을 알 수 있다.

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int G = Integer.parseInt(br.readLine());

        int left = 1, right = 2;

        StringBuilder sb = new StringBuilder();
        while (left < right) {
            int diff = (int) (Math.pow(right, 2) - Math.pow(left, 2));
            if (diff > G)
                left++;
            else if (diff < G)
                right++;
            else {
                sb.append(right).append("\n");
                left++;
                right++;
            }
        }
        if (sb.length() == 0)
            sb.append(-1).append("\n");

        sb.delete(sb.length() - 1, sb.length());

        System.out.print(sb);
    }
}