백준 1789 C++ 시간초과

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

1789번: 수들의 합

 

간단한 정답 코드

#include <iostream>
using namespace std;

int main() {
    long S, sum = 0, result = 0;
    cin >> S;
    
    for (int i = 1; sum <= S; i++) {
        sum += i;
        result = i;
    }

    cout << result - 1;
    return 0;
}

 

int로 하고 시간초과 나서 뭐가 문제지... 하고 이분탐색 형식으로도 풀었다

#include <iostream>
using namespace std;

int main() {
    long S;
    cin >> S;
    long result, start = 0, end = s;
    while(start <= end) {
        long mid = (start + end) / 2;
       
        if(mid * (mid+1)/2 <= S) {
            result = mid;
            start = mid+1;
        }
        else {
            end = mid-1;
        }
    }
    cout << result;
}

 

알고리즘 쓰지도 않은 듯

간단하다! 더해지는 수의 개수가 가장 많아야 하니까 가장 작은 수 부터 더해주다가 누적 값이 S을 넘는 순간 반복문을 빠져나오고 더하던 i 값에서 하나를 빼주면 누적 값은 안 넘고 최대 N이 나오는 방식이다!

 

시간초과 나는 이유

S의 최댓값이 unsigned int 최댓값이기 때문에, 1~n 꼴의 합이 되면서 S보다 큰 수를 찾으면 그 수는 int 범위를 벗어날 수 있습니다.

=> 그냥 int 말고 long 함 써보시라... 바로 정답일수도!!!