[Java] 백준 1484번 : 다이어트

문제

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

 

접근 방법

1. 브루트포스로 풀 수 있지만 그랬을 경우 O(N^2)으로 시간 초과가 발생한다.
2. 따라서 반복문을 줄일 수 있는 방법으로 투포인터를 생각했다.
3. 그리고 문제는 살이 찐 경우만 체크하면 된다. (값이 자연수이다.)
4. 따라서 포인터를 두고 앞에서부터 탐색하는 방법으로 문제를 풀었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int G;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

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

    //실행
    public static void process() {
        long s = 1;
        long e = 2;

        boolean flag = false;
        
        
        //범위를 500001까지 한 이유는 50000*50000-49999*49999 하면 99999가 나온다. 따라서
        //G범위가 10보다 작거나 같으므로 10만까지 가지 않아도 된다.
        while(e<50001){
            long difS = s*s;
            long difE = e*e;

            if(difE-difS == G){
                sb.append(e).append("\n");
                flag = true;
                s++;
                e++;
            }else if(difE-difS<G){
                e++;
            }else{
                s++;
            }
        }

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


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}