[알고리즘] 백준 1789 - 수들의 합

1. 문제

https://www.acmicpc.net/problem/1789
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

2. 입력

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

3. 풀이

매개변수탐색(이분탐색)으로 풀 수 있다.

1. 문제 뒤집기

원래 문제

• 조건 : S를 알 때
• 타겟 : 자연수 N의 최댓값은?

뒤집은 문제

• 조건 : 자연수 N이 주어졌을 때
• 타겟 : N개의 자연수 합이 S를 만족하는가?

2. 공식

N개의 서로 다른 자연수로 합을 만들 때 N이 최대가 되기 위해서는
자연수들이 작은 숫자부터 차례대로 있어야 한다.

1~N까지 순서대로 있는 자연수의 합 공식은 다음과 같다

• 짝수 : (1+n)*n/2
• 홀수 : ((1+n)*(n/2))+(n+1)/2

ex) 1~10까지 일때
(1+10) + (2+9) + ...+(5+6) = 11*5 = 55

따라서 N개로 만들 수 있는 값의 범위는 다음과 같다

• 짝수 : (1+n)n/2 <= S < (1+(n+1))(n+1)/2
• 홀수 : ((1+n)(n/2))+(n+1)/2 <= S < ((1+(n+1))((n+1)/2))+((n+1)+1)/2

1~N으로 만들어지는 값과 1~N+1로 만들어지는 값 사이의 범위가 N개의 자연수로 만들 수 있는 숫자 범위가 된다.

3. 이분 탐색

2번의 공식을 이용해서 모든 N에 대해 이분 탐색을 진행한다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class sum_1789 {

    static long s;

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        s = Long.parseLong(bf.readLine());

        //이분탐색

        long left = 1;
        long right = s;

        long answer = 0;

        while(left<=right){
            long mid = (left+right)/2;

            if(determination(mid)){
                answer = mid;
                left = mid+1;
            }
            else{
                right = mid-1;
            }
        }
        System.out.println(answer);
    }

    public static boolean determination(long n){

        //짝수일 때
        if(n%2==0){
            return s>=(1+n)*n/2;
        }
        //홀수일 때
        else{
            return s>=((1+n)*(n/2))+(n+1)/2;
        }

    }
}