BOJ 23631 C++

문제접근

우선 이문제는 등차수열의 합을 이용하는 문제입니다.
우선 시간초과가 나지 않으려면 이분탐색 최대 범위를 5000으로 해야합니다.

5000*(5000 + 1) / 2

가 10,000,000보다 크기때문입니다. *등차수열을 이욯하기 때문에.
이 문제에서 이분탐색 해야하는 값은 n보다 크거나 같은 등차수열입니다.
문제의 예시를 보면 살펴볼 수 있죠.
3,6,9.. 등차수열을 코드로 나타내면 다음과 같습니다.

K * (N*(N + 1) / 2);

즉 N의 값이 이동한 횟수가 되겠네요. 그러므로 N의 값을 이분탐색으로 찾아줘야합니다.
그리고 이동한 횟수를 이용하여 좌표의 값을 구할 수 있습니다.
문제 예시에서 볼 수 있듯이 홀수면 양수이고 짝수면 음수입니다.
그리고 좌표의 값은 이동횟수에 비례하는걸 볼 수 있습니다.
이동횟수가 2일때는 첫번째 이동에 3만큼 이동하고 두번째 이동에 6만큼 다시 왼쪽으로 움직이기에
x좌표 0에서 오른쪽으로 3이동하고 왼쪽으로 6이동했으므로 3이랑 -3이네요.
3번째와 4번째 이동은 9만큼 다시 오른쪽으로 이동 12만큼 왼쪽으로 이동하기에 6이랑 -6의 값이 x좌표네요.
여기서 알 수 있듯이

좌표 = K * ((이동횟수 + 1) / 2);

이동한 횟수가 짝수면 -붙여줍니다.
이제 알건 다 알았습니다.
그럼 멈춰야할 좌표는 이렇게 구할 수 있죠. 문제에서 n보다 적게 뛰어야하므로 n-1에서 이분탐색으로 구한 크거나 같은 등차수열중에 사용할 가장작은 이동횟수인 값을 구했습니다.

n보다 덜뛰는거리 (n-1) - (이동횟수 등차수열) = 뒤로가야하는 거리

뒤로가야하는 거리를 알았죠 이동횟수로 좌표값을 알아냈으니 거기서 더하면(음수가 나오기에) 멈춰야 하는 x좌표가 나옵니다. 반대로 현재 좌표가 음수일때는 빼야겠네요.

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;

// ebun 함수 : 이동횟수를 구하는 함수
int ebun(int n, int k)
{
    int lo = 0;
    int hi = 5000;

    // 이진 탐색으로 이동횟수 구하기
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        ll cal = mid;
        cal *= mid + 1;
        cal *= k;
        if (cal < 2 * n)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return lo;
}

// sol 함수 : 최종 결과를 반환하는 함수
string sol(int n, int k)
{
    // 이동횟수 구하기
    int LR = ebun(n, k);

    // 위치(pos) 구하기
    int pos = 0;
    if (LR % 2 == 0)
    {
        // LR이 짝수인 경우, 왼쪽으로 이동하는 것이므로 pos는 음수가 됨
        pos = -k * ((LR + 1) / 2);
        pos -= (n - 1 - (LR * (LR + 1) * k / 2));
        return to_string(pos) + " L";
    }
    else
    {
        // LR이 홀수인 경우, 오른쪽으로 이동하는 것이므로 pos는 양수가 됨
        pos = k * ((LR + 1) / 2);
        pos += (n - 1 - (LR * (LR + 1) * k / 2)); //빠꾸쳐야하는거리
        return to_string(pos) + " R";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;

    // 각 테스트 케이스에 대해 sol 함수 호출하여 결과 출력
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        cout << sol(n, k) << "\n";
    }

    return 0;
}