오늘의 학습 키워드

• 특정 k 값을 찾는 것 = 이분탐색으로 구현
• 자료형의 범위에 대하여 숙지하자
• C++의 경우, 연산 중간 과정에서 오버플로우가 발생할 수 있으므로 자료형 선택에 주의가 필요

[백준] 징검다리 - 11561

• [백준] 징검다리 - 11561
• Silver III
• C++ 풀이

문제해설

입력값 N이 누적합 sumN(n)이 만족하는 n의 최대값을 찾는 문제이다.

접근법: 이분 탐색

단순히 만족하는 값을 찾는 것이 목표인 경우, 이분 탐색이나 브루트포스를 사용해 원하는 조건을 충족하는 최대 n을 찾는 방법이 타당하다.

• N의 최대 범위가 $10^{16}$ 이기 때문에 시간복잡도 Olog(N)인 이분 탐색으로 접근한다.
• 정수형의 타입은 long long으로 정의해야 오버플로우가 발생하지 않는다.

참고: end의 초기 값을 설정할 때는 N = 10^16의 결과를 직접 확인하여 end 값을 대략적으로 잡아도 무방하다.
실제로 N = 10^16일 때, n = 141,421,355이었고, end는 러프하게 1,000,000,000으로 초기화했다.
굳이 머리 아프게 계산하지 말자..ㅎ

참고: mid가 int라면, sumN이 long long이어도, 후항 계산 과정에서 이미 오버플로우가 발생하여 잘못된 값이 전달된다. 따라서, 두 변수 모두 long long으로 정의해야한다.

sumN = mid * (mid + 1) / 2;

* (추가) start, end, mid 모두 long long으로 정의했지만 mid를 제외한 start, end는 int로 정의해도 무관하다.

#include <iostream>
using namespace std;

int main(){
    int T; cin >> T;
    while(T--){
        long long answer = 0, sumN, N;
        cin >> N;

        long long start = 1, end = 1000000000, mid;
        while (start <= end){
            mid = (start + end) / 2;
            sumN = mid * (mid + 1) / 2;
            if (sumN <= N){
                start = mid + 1;
                answer = mid;
            }
            else {
                end = mid - 1;
            }
        }
        cout << answer << "\n";
    }
}

오늘의 회고

어떤 변수들까지 long long으로 정의해야하나 고민을 했다.
start, end, mid의 최대값이 정수형 int안에 세이프되기 때문에 int로 정의해도 된다고 판단했지만 잘못된 판단이었다.
c++의 경우, 자료형을 정의할 때, 해당 변수의 최대값 뿐만 아니라, 해당 변수를 가지고 연산하는 과정에서 오버플로우가 발생할 수 있다는 것을 명심하자!