[실전 문제] 2차식 정답 추측

1. 문제

2차식 f(x) = x*x+ x 가 있고, 숫자 a가 주어진다. 우리는 f(x) = a 를 만족하는 x의 값을 찾고 싶지만, 보통 이 값은 정수로 떨어지지 않는 경우가 많다. 예를 들어, f(x) = 20 을 풀고자 한다면, x = 4이기 때문에 이는 정수이지만, f(x) = 103 을 풀고자 한다면 이는 x = 9.6612... 로써 정수가 아니다.

 

이 문제에서는 x의 정수부분이 얼마인지를 구하는 프로그램을 작성하시오. 단, x 는 음수를 제외한 정수이다. 예를 들어, f(x) = 103 을 풀고자 한다면, x = 9.6612... 이기 때문에 정수부분은 9가 된다.

---

입력

첫 번째 줄에 숫자 a가 주어진다. ( 1 ≤ a ≤ 1,000,000,000,000,000,000 ) 

출력

f(x) = a 를 만족하는 음수를 제외한 정수 x의 정수부분을 출력한다. 

예제 입력

103

예제 출력

9

 

 

 

2. 풀이

이 문제는 어렵게 생각하지 않는다면 쉽게 풀 수 있는 문제이다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        long a = Long.parseLong(br.readLine());

        long idx = 0;
        while(idx * idx + idx <= a) {
            idx++;
        }

        bw.write(idx-1 + "");

        br.close();
        bw.flush();
        bw.close();
    }

}

하지만, 문제의 의도대로 이진 탐색을 이용하여 푼다면 다음과 같이 풀 수 있다.

 

우선 x가 1부터 10까지일 경우를 계산해보면 다음과 같다.

1	2	3	4	5	6	7	8	9	10
2	6	12	20	30	42	56	72	90	110

여기서 예제의 값인 103을 구한다고 했을 때, 9에서 10사이에 있음을 알 수 있다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        long a = Long.parseLong(br.readLine());
        binarySearch(a);

        br.close();
    }

    private static void binarySearch(long a) {
        long min = 0;
        long s = 0;
        long e = (long)Math.sqrt(1000000000000000000L);

        while(s <= e) {
            long mid =  (s + e)/2;
            long result = mid * mid + mid;

            if(result > a) e = mid - 1;
            else if(result < a) {
                s = mid + 1;
                if(min < mid) {
                    min = mid;
                }
            }
            else {
                min = mid;
                break;
            }
        }

        System.out.print(min);
    }

}
/*
 a 범위: 0 이상, 1000000000000000000 이하
 long 자료형 범위 : -9223372036854775808 이상, 9223372036854775807 이하
 */