[C++] 백준 1789번 -수들의 합 (이진 탐색)

문제 링크 : www.acmicpc.net/problem/1789

1789번: 수들의 합

 

 

 

문제

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

입력

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

출력

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

 

 

접근 방법

 

서로 다른 자연수를 더해서 S를 만드는데, 이때 어떻게 해야 그 서로 다른 자연수들의 개수가 최대가 될까 생각해보았다.

결론은 1부터 차례로 2, 3, 4, ,,,,씩 더해야 '서로 다른' 과 '최대 개수' 조건을 만족한다. 자연수들의 차를 1씩으로 최대한 작은 수들로 더해야 S를 최대한 여러개의 자연수 합으로 나타낼 수 있기 때문이다. 

 

즉 1부터 x까지 자연수를 더한수가 S보다 크거나 같아질 때 x-1이 답이 된다. 

//
//  BS_BOj1789_수들의 합.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/26.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <cmath>
using namespace std;
 
 
int main(){
    
    long S; cin >> S;
    
    long ans = 0;
    long x = sqrt(2*S);
    for(long i = x; i>=1; i--){
        if(i*i + i <=2*S){
            ans = i;
            break;
        }
    }
    cout << ans;
    
    return 0;
}

 

 

 

이 문제를 이진 탐색으로 풀어보자.

start = 1, end = S로 잡고 start 부터 end의 중간값을 mid로 잡는다. 

1부터 mid까지의 합(mid*(mid+1) / 2)을 구한다.

    1) 그 값이 S보다 크면 mid 값이 더 작아져야 하므로 end 를 줄인다. (end = mid-1로 지정한 뒤 다시 탐색)

    2) 그 값이 S보다 작거나 같으면 mid 값이 더 커져야 하므로 start를 키운다. (start = mid+1로 지정한 뒤 다시 탐색)

 

참고로 이진탐색은

원소가 정렬되어 있어야 하며, 각 원소에 랜덤 액세스가 가능할 때 적용할 수 있다. 우리는 정렬된 자연수를 고려하므로 이진탐색을 적용할 수 있다.

 

//
//  BS_BOj1789_수들의 합.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/26.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <cmath>
using namespace std;
 
 
int main(){
    
    long S; cin >> S;
    
    long ans = 0;
    long start = 1; long end = S;
    
    while(start<=end){
        long mid = (start+end)/2;
        
        if(mid*(mid+1)/2 <= S){
            ans = mid;
            start = mid+1;
        }
        else{
            end = mid-1;
        }
    }
    
    cout << ans;
    
    return 0;
}