코드트리 [자바 java] 자연수 n개의 합

https://www.codetree.ai/missions/8/problems/sum-of-n-natural-numbers?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

s가 주어지고, 1부터 n까지의 합이 s가 넘지 않는 n의 최댓값을 구하는 문제이다.

 

나는 이진탐색으로 위 문제를 풀었다.

기본적인 이진탐색과 같이 왼쪽, 오른쪽을 의미하는 변수를 설정하고, 중간값을 계속해서 탐색하며 중간값의 합이 s보다 작으면 left를 갱신하고, s보다 크면 right를 갱신했다. 1부터 mid의 합이 s와 같다면 mid가 답이므로 이를 출력하고 break한다.

 

이 때 주의할 점은 left값이 s보다 작을 때의 최솟값을 구하는 것이므로, 만약 mid의 합이 s보다 작다면, mid + 1의 합이 s보다 큰지 알아본다. 크다면, 현재의 mid가 답이므로 이를 출력하고 break한다.

 

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long s = Long.parseLong(br.readLine());

        int left = 0;
        int right = 100000;
        int mid = 0;

        while(left <= right){
            //mid의 값을 찾고, 이 값이 s보다 크거나 작은지 확인한다.
            mid = (left + right)/2;

            long midSum = (((long)mid)*(long)(mid+1))/2;
           // System.out.println(midSum);

            if(midSum == s){
                 System.out.println(mid);
                break;
                
            }
            else if(midSum < s){
                 if(((long)(mid+2)*(long)(mid+1))/2 > s){
                    System.out.println(mid);
                    System.exit(0);
                }
                else left = mid + 1;
            }
            else{
                 right = mid -1;
            }

        }

    }
}