[알고리즘] 백준 1789번: 수들의 합 (C++)

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

처음에 고안했던 방법은 수를 선택 여부에 따라 백트래킹하여 s가 되게끔 만족하는 수의 개수 중 최댓값을 도출하려 했다.

>> 하지만, 이는 엄청난 경우의 수에 따른 메모리 초과뿐만 아니라 결괏값도 도출하지 못했다.

#include <iostream>
using namespace std;

int maxValue = 0;
unsigned int s;

void solve(unsigned int num, int cnt, int plus){
    if(num == s){
        maxValue = max(maxValue, cnt);
        return;
    }
    
    solve(num + plus, cnt + 1, plus + 1);
    solve(num, cnt, plus + 1);
}

int main(){
    cin >> s;
    
    solve(0, 0, 1);
    //cout << "func end";
    cout << maxValue;
    return 0;
}

---

솔루션

이 문제를 수학적으로 접근한다면 쉽게 풀 수 있었다.

 

서로 다른 N개의 자연수, N의 최댓값이다. 

S를 1부터 작은 수부터 계속 넣다 보면 최댓값을 만들 수 있지 않은가?

예를 들어 200을 1부터 계속 채워 넣으면

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

1~20까지 다 더하면 210으로 200을 넘는다.

1~19까지 다 더하면 190인데

1~18까지 더하고, 19를 29로 바꾼다면 200이 되지 않는가?

다음 수들을 다 더하는 것 >> {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 29}

 

이와 같은 방법으로 답을 도출하면 되는 문제였다.

허나, 범위가 넓기 때문에 이분 탐색을 사용한다.

정렬과도 상관없으므로 이분 탐색을 사용할 수 있는 조건도 된다.

---

궁금한 점

이분 탐색을 사용해도 시간 초과가 나서 long long으로 잡아두었던 타입들을 long으로 교체해주니 시간 초과가 일어나지 않고, 통과하였다. 타입이 시간에 무슨 영향을 끼치는 건가?

 

[AC 코드]

#include <iostream>
#define ll long
using namespace std;

ll s;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> s;
    
    ll low = 1;
    ll high = s;
    
    ll result;
    while(low <= high){
        ll mid = (low + high) >> 1;
        
        ll sum = (mid + 1) * mid / 2;
        
        if(sum <= s){
            low = mid + 1;
            result = mid;
        }
        else{
            high = mid - 1;
        }
    }
    
    cout << result;
    return 0;
}