[백준 1789] 알고리즘 63일차 : 수들의 합

www.acmicpc.net/problem/1789

1789번: 수들의 합

C++ 이분탐색..

16분전. 시간에 쫓기고 있습니다.

이분탐색인데 이분탐색으로 안해도 풀리네요.

문제 한문장 대로 서로다른 N개의 자연수의 합이 S가 될때 N의 최댓값을 구하는 문제

 

접근방법

합이 S가 되는 수들의 개수가 최대가 되려면 적은 수부터 연속된 수를 더하는 경우가 가장 최대가 되겠죠.

그래서 우리가 알고 있는 공식 1부터 N까지 연속된 수의 합을 구하는 공식인 N(N+1)/2 을 활용하면 됩니다.

이 N에 들어가는 수를 이분탐색으로 탐색하면 시간이 더 적게 들겠지만 1부터 차례로 대입해가면서

공식의 값이 S를 넘을때 N-1개가 개수의 최대 값이 됩니다. 근데 1일때는 반복문을 안들어가게 돼서 예외처리 해줬습니다.

 

소스코드

#include <iostream>
using namespace std;
long long S;
int main(){
    cin >> S;
    for(long long i = 1; i <= S ; i++){
        if( ((i*(i+1)) / 2) > S ){
            cout << i-1;
            return 0;
        }
    }
    cout << 1;
    
    return 0;
}

이건 코드 길이가 좀 길어졌지만 이분탐색으로 풀이한 코드

소스코드

#include <iostream>
using namespace std;
long long S;
bool isOver(long long n){
    return ((n*(n+1)) / 2) > S ? true : false ;
}
long long binarySearchMax(long long s, long long e){
    long long mid = 0;
    while(s <= e){
        mid = (s+e)/2;
        if(isOver(mid)){
            e = mid-1;
        }else{
            s = mid+1;
        }
    }
    return s-1;
}
int main(){
    cin >> S;
    cout << binarySearchMax(1, S);
    
    return 0;
}