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

문제

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

---

풀이(23분)

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {

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

        int g = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        int i = 1;
        // (1)
        while (true){ // 배열의 크기를 구하기 위함
            if(Math.pow(i,2) - Math.pow(i-1,2) <= 100000){
                i++;
                continue;
            }
            break;
        }
        int[] arr = new int[i];
        int start = 1;
        int end = 2;
        for(int x = 1; x < i; x++){
            arr[x] = x;
        }
        
        // (2)
        // 투포인터 구현
        while(end <= i-1 && start <= i-1){
            long first = (long) Math.pow(arr[start], 2);
            long second = (long) Math.pow(arr[end], 2);
            if(second - first == g){ // 조건을 충족하는 경우
                queue.add(end);
                start++;
                end++;
                continue;
            }
            if(second - first < g){ // 예상보다 적은 경우
                end++;
                continue;
            }
            if (second - first > g){ // 예상보다 큰 경우
                start++;
            }
        }
        int size = queue.size();
        if(size == 0){
            System.out.println(-1);
            return;
        }
        for(int x = 0; x < size; x++){
            System.out.println(queue.poll());
        }
    }
}

 

문제 해결 자체는 투포인터로 진행하여 어렵지 않게 구현했으나 자료형에 대한 실수를 해서 시간을 다소 소비했다.

 

1. arr의 크기를 구해야한다.

코드의 주석 (1) 부분을 보자. 인접한 두 수의 제곱의 차를 구하여 100,000을 만족시키는 최댓값을 구한다.

1-1. 이렇게 하는 이유는 문제를 접한 초반 100000이라는 최댓값이 있으니 단순하게 100 or 1000정도가 배열의 최대겠구나라고 생각했다. 하지만 각각 계산해보면 10,000과 1,000,000으로 100,000의 값을 만족시키지 않았기에 다른 함정이 있겠구나 생각했다.

1-2. 따라서 인접한 두 수의 제곱의 차에 대하여 최대 몇까지 가능하며 그것이 배열의 크기이겠구나라고 생각했다. 위를 따라 구하게 되면 50000^2 - 49999^2 가 99999로 최대가 되는 것을 알 수 있다.

 

2. 이 후 투포인터로 문제를 해결한다.

2-1. first와 second라는 제곱에 대한 계산을 하며 50000^2 는 25억이다. 하지만, 단순하게  10000^2은 1억이니까 문제 없겠지 하고 int 자료형을 사용하여 오류가 발생했었다.