[JAVA] BOJ(백준) 1484 다이어트

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

1484번: 다이어트

 

수학과 투 포인터 문제다.

 

성원이의 몸무게가 G 킬로그램 늘었다.

이 G킬로그램은 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

입력은 자연수로 들어오므로 모든 몸무게는 자연수다.

 

처음 생각한 방법은 어떤 수의 제곱에서 g를 뺀 수도 제곱수라는 점을 활용하는 것이다.

반복문으로 1부터 g까지 순회하면서 해당 수의 제곱에서 g를 빼고 그 수(tmp)가 제곱수 인지 확인했다.

tmp가 0보다 작은 경우는 제곱수가 아니므로 continue 했다.

 

이 방법은 실패했다.

두 가지 이유가 있다.

 

1. g까지 순회하지 않아도 된다. (g+1)/2 까지만 순회하면 된다

g = x ^2 - y^2 = (x + y)(x - y)로 몸무게의 최대 값은 g의 반이다.

 

2. tmp가 0인 경우에도 continue를 해야한다.

tmp가 0이라는 것은 몸무게가 0인 것이다.

 

해당 부분을 고치니 for문으로 성공하였다.

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

public class Main {

    static long n;
    static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        long bound = (n + 1) / 2;
        
        for (long i = 1; i <= bound; i++){
            long tmp = i * i - n;
            if (tmp <= 0){
                continue;
            }

            double tmpSqrt = Math.sqrt(tmp);
            long tmpLong = (long)tmpSqrt;

            if (tmpSqrt == tmpLong){
                flag = true;
                System.out.println(i);
            }
        }

        if (!flag) System.out.println(-1);
    }
}

 

for문으로 해결하기 전 오류를 맞이하고 투 포인터 방법을 생각했다.

제곱수의 규칙을 보니

1 4 9 16 25 ... (제곱수)

1 3 5 7 9 ... (제곱수 증가 폭)

제곱수의 증가 폭이 2씩 증가한다는 점을 알았고

이것의 누적합이 제곱수인 것을 확인했다.

 

처음에는 투 포인터를 이용하여 제곱 수의 차이가 g인 것을 찾기 위해 증가 폭 누적합을 사용하려 했고 배열을 만들었다.

배열에 증가 폭에 맞게 저장을 했는데, 저장을 하다보니 그 값이 제곱수라는 것을 알게 되었고 증가 폭과 상관 없이 i * i를 저장했다.

이 또한 인덱스의 제곱이므로 배열이 필요하지 않다는 것을 깨달았다.

 

g는 자연수이므로 현재 몸무게와 상상의 몸무게가 같을 순 없다.

left = 1, right = 2에서 시작해 투 포인터를 이용했다.

right * right  - left  * left 의 값을 계산해서 이 값이 g와 같으면 출력하고

작으면 right을 증가, 크면 left  을 증가했다.

 

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

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

        int left = 1;
        int right = 2;
        int cnt = 0;

        while (left <= (n+1)/2 && right <= (n+1)/2 && left <= right){
            int g = (right * right) - (left * left);
            if (g == n){
                System.out.println(right);
                cnt++;
                left++;
            } else if (g < n){
                right++;
            } else {
                left++;
            }
        }

        if (cnt == 0){
            System.out.println(-1);
        }
    }
}