[BOJ] 23631: 진심 좌우 반복뛰기

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

BOJ - 진심 좌우 반복뛰기

문제 유형 : 수학, 구현

문제 난이도 : Silver I

 

문제

히어로 협회에는 아래와 같은 두 가지 소문이 있다.

1. 진심 좌우 반복 뛰기를 10100$10^{100}$일 동안 반복하면 히어로가 된다.
2. 뛴 거리의 총합이 N$N$m 이상이면 대머리가 된다.

지나가던 제로x는 소문을 듣고 진심 좌우 반복 뛰기를 하기로 결심했다. 진심 좌우 반복 뛰기는 간단하다.

• 위치 x=0에서 시작하여, 처음에는 오른쪽으로 Km를 뛴 다음 방향을 바꾼다.
• 방향을 바꿀 때마다 이전에 움직인 거리에 Km만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.

예를 들어, K=2 라면, 오른쪽으로 2m, 왼쪽으로 4m, 오른쪽으로 6m, ...

하지만, 제로x는 대머리가 되는 것이 너무나도 싫었다. 즉, 소문에 따라 뛴 거리의 총합이 N$N$m 이상이 되지 않아야 한다. 대머리가 되지 않으면서도 운동의 효과는 보고 싶었던 제로x는 정확히 (N−1)m만 뛸 것이다.

하지만 제로x는 어디서 멈춰야 하는지 계산할 수 없었다. 제로x가 대머리가 되지 않도록 도와주자!

 (N−1)m를 뜀과 동시에 전환점에 도달할 경우, 방향을 바꾸고 멈춘다. 예제 1의 두 번째 테스트 케이스를 참고하자.

 

입력

첫 번째 줄에 테스트 케이스 수 T가 주어진다. 두 번째 줄부터 T개의 줄에는 자연수 N,K가 공백으로 구분되어 주어진다.

•  1≤T≤100,000
•  1≤N,K≤10,000,000

출력

제로x가 멈춰야 하는 x좌표와 바라보고 있게 될 방향을 출력한다. 방향을 출력할 때 오른쪽은 R, 왼쪽은 L로 나타낸다.

 

풀이

제로 x는 정확히 n-1회 움직여야 한다.

한 방향에서 다음 방향 전환까지 점프하는 횟수를 m이라고 했을 때,

이를 k번 반복하면 k * (m+1) * m / 2이다.

이 횟수가 n-1을 넘으면 안되는데, 식은 다음과 같다: k * (m + 1) * m / 2 <= N

이때 m의 최대값은 m에 대한 2차방정식의 근의공식으로 양의정수 해를 구해서 소수부분을 자른 값이다.

즉, m = (int)( (-1 + sqrt(1 + 8*N/k))/2)이다. (N을 입력받고 처음에 1을 뺀다고 가정하자.)

 

m번의 루틴 이후에, 남은 거리는 

N - (m(m+1)/2) * k이다.

그리고, 제로x의 위치는 ((m-1)/2 + 1) * k * (m%2 == 1? 1:-1)이다.

즉, 루틴 2회에 한 사이클이라 했을 때, 사이클의 횟수 * k인데, 여기에 루틴의 횟수가 짝수인 경우, 음수 위치이므로 -1을 곱한다.

 

만약 m번의 루틴의 횟수가 홀수라면, 이제 왼쪽으로 가는 도중에 멈추므로, {pos - leftLen, 'L'}이다.

짝수라면, 오른쪽으로 가는 도중에 멈추므로, {pos + leftLen, 'R'}이다.

코드

C++

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main () {
    int t;
    cin >> t;

    vector<pair<int, char>> ans;
    int n, k;
    for (int i = 0; i < t; ++i) {
        cin >> n >> k;
        n--;
        // base case: 첫 방향전환 전에 끝나는 경우
        if (n < k) {
          ans.push_back({n, 'R'});
          continue;
        }

        int m = int(-1 + sqrt(1 + (8 * (float)n / (float)k))) / 2;
        int len =  k * (m * (m+1) / 2);

        int leftLen = n - len;
        int pos = ((m-1)/2+1) * k * (m % 2 == 1? 1 : -1);
        if(m % 2 == 1) {
          ans.push_back({pos - leftLen, 'L'});
        } else {
          ans.push_back({pos + leftLen , 'R'});
        }
    }

    for (const auto &c : ans) {
        cout << c.first << " " << c.second << "\n";
    }

    return 0;
}