[백준 1789] 수들의 합 - JAVA // le_effort

수들의 합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	13088	5373	4536	42.877%

문제

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

예제 입력 1 복사

xxxxxxxxxx
200

예제 출력 1 복사

xxxxxxxxxx
19

 

 

 

풀이

N의 최댓값을 찾으려면 어떻게 해야 할까?

 

예를들어 200이라는 숫자를 보자

 

주어진 문제의 조건에서 서로 다른 N개의 자연수라고 했으니

 

N개를 최대한 많이 얻기 위해서는 1부터 시작해야 되는것은 자명하다.

 

200의 경우

1~19까지의 합은 190이다

 

이 때 190은 200이 되려면 10이 부족하지만 숫자 10은 위에서 이미 사용해서 조건에 위배된다.

 

그럼 1~18의 합은 몇일까? 이를 계산해보면

171이 나온다.

 

이 때 200 - 171을 하면 29가 나오는데

숫자 29 한개를 넣으면 문제를 풀 수가 있다.

 

그래서 이분탐색으로 mid를 숫자값으로 잡고 풀었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    
    static int s;
    static long ans=0;
    public static void main(String[] args) throws  IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        s = Integer.parseInt(br.readLine());
        
        int start = 1;
        int end = s;
        
        while(start<=end) {
            int mid = (start+end)/2;
            long sum = 0;
            
            sum = (1+mid)*mid;
            sum/=2;
            
            
            long tmp = s-sum;
            
            if(tmp > mid) {
                ans = Math.max(ans, mid);
                start = mid+1;
            }
            else {
                end = mid-1;
            }
        }
        System.out.println(ans+1);
    }
}
​