[백준] 1789. 수들의합 (Java) [이분탐색]

문제

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

1789번: 수들의 합

 

알고리즘

이분탐색 + 수학

 

풀이

N까지의 합의 공식과 이분탐색을 이용해서 풀이를 했다.

left+ right/2, 즉, 중간 값을 구해서 S를 찾아가는 과정이며

자세한 건 풀이를 보자.

 

 

코드

package com.company;

import java.io.*;

public class Test_BinarySearch {
    static long MAX = 4294967295L;
    static long ans = 0;

    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long S = Long.parseLong(bf.readLine());
        long left = 0;
        long right = MAX;
        while (left <= right) {
            long mid = (left + right) / 2;

            if (((mid * (mid+1)) / 2) > S){
                right = mid-1;
            }else{
                left = mid+1;
                ans = mid;
            }
        }
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
    }
}

 

이분탐색이 아닌 1중 for문을 이용해서 풀이를 하는 방법도 있는 것 같다.

https://zzang9ha.tistory.com/147