[백준] 1484 다이어트 - Java

 

 

 

문제 출저

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

1484번: 다이어트

 

 

 

문제 풀이

성원이는 다이어트 중이다. 성원이의 현재 몸무게의 제곱 - 기억하는 몸무게의 제곱 = G 이다. 

이 때 G를 만족하는 현재 몸무게를 구해야 한다. 

 

투 포인터를 이용해 풀었습니다.

long e : 현재 몸 무게 

long s : 기억하는 몸 무게

 

이렇게 두 개의 포인터를 사용하여 

e*e - s*s <= G 이면 e++ 

e*e - s*s < G 이면 s++ 

e*e - s*s == G 이면 정답을 출력했습니다.

 

이 때, e의 범위를 정하는 것이 중요했습니다.

e의 최댓값은 다음 수식을 만족해야 합니다.

 

e^2 - (e-1)^2 = G 

이 수식을 풀면 2e = 100_001 이 나옵니다.

e의 최대 범위가 50000이 나오는 것을 알 수 있습니다.

 

50000의 제곱은 int 범위를 넘어가므로 long으로 선언했습니다.

 

 

 

소스 코드

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


/*
다이어트
https://www.acmicpc.net/problem/1484

g <= 100_000
g = 현재 몸무게 제곱 - 기억하고 있는 몸무게 제곱

y : 현재 몸무게
x : 기억하고 있는 몸무게

y^2 - (y-1)^2 = 100_000 이 y의 최대값이다.
y^2 - Y^2 + 2y - 1 = 2y = 100_001
50_000 이 나온다.

9% 틀림
s의 초기값을 0으로 주어서 발생했다.
몸무게가 0일리는 없으니 1로 바꾸었다.


 */

public class Main {

    static int g;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        g = Integer.parseInt(br.readLine());

        long s = 1;
        long e = 2;

        boolean flag = false;

        while(e <= 50000) {
            long perS = s*s;
            long perE = e*e;

            long searchG = perE - perS;

            if(searchG == g) {
                System.out.println(e);
                flag = true;
            }

            if(searchG > g) {
                s++;
            }
            else {
                e++;
            }
        }

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

    }

}