[알고리즘 풀이 분석] BOJ 1789 수들의 합

오늘의 두번째 문제는 BOJ 1789 수들의 합 이다! 실버 5 문제이고 기본적인 이분탐색 문제를 연습해보았다!

BOJ 1789 수들의 합

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

입출력

• 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
• 첫째 줄에 자연수 N의 최댓값을 출력한다.

입력	출력
200	19

나의 풀이

이 문제에서 이진 탐색의 기준이 되는 것은 N의 값이라는 것은 당연했고 '서로다른 N개의 자연수의 합' 이라는 말에 잠시 속을 뻔 했지만 N의 최댓값을 구해야 하기 때문에 결국에는 1부터 시작하는 합 (N*(N+1)/2) 을 구해가면서 접근해야 한다고 생각했다.

시작 전 left right의 값은 각각 1, S 에서 시작하고 그 중간 값 mid = (left+right)/2 을 구해 1부터 mid 까지의 합이 S 보다 작다면 left를 조절, 크다면 right를 조절하면서 left, right 가 역전될 때 까지 이분 탐색을 진행했다.

이 때 정답을 도출하는 시점이 조금 헷갈렸는데, 나는 N(N+1)/2 <= S < (N+1)(N+2)/2 가 되는 N 값을 구하는 것이었으므로 left 를 조절할 때 마다 해당 시점의 중간 값을 저장하는 것으로 진행했다.

코드

c++

#include <iostream>

// BOJ 1789 수들의 합, 이진 탐색 사용
using namespace std;

long long solution(long long S) {
    long long answer;
    long long left = 1, right  = S;

    while (left<=right){
        long long mid = (left+right)/2;
        if (mid*(mid+1)/2 > S) right = mid-1;
        else {
            answer = mid;
            left = mid+1;
        }
    }

    return answer;
}

int main() {
    long long S, ans;

    cin>>S;
    ans = solution(S);

    cout<<ans;

    return 0;
}

swift

import Foundation

func solution(_ S:Int) -> Int {
    var answer = -1
    var left = 1
    var right = S
    
    while left<=right {
        let mid = (left+right)/2
        
        if mid*(mid+1)/2 <= S{
            answer = mid
            left = mid+1
        }else{
            right = mid-1
        }
    }
    
    return answer
}

let S = readLine()

if let s = S {
    let answer = solution(Int(s)!)
    print(answer)
}