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

키워드

• 위치 x = 0에서 시작하여, 처음에는 오른쪽으로 Km를 뛴 다음 방향을 바꾼다.

• 방향을 바꿀 때마다 이전에 움직인 거리에 Km만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.

• 정확히 (N - 1)m만 뛸 것

---

구현

• 다음을 정의하자.
  • 전부 뛴다 → 해당 뛰여야할 길이만큼을 전부 뛴다.
  • n
    • 전부 뛴 횟수

• 전부 뛸 수 있는 n값을 구한다.
  • low = 0
  • high = 5000
    • (5000)(5000+1)/2 ≥ 10,000,000 이므로 5000을 상한선으로 정했다.
  • n을 매개변수로 하여, 이분 탐색으로 진행한다.
  • 숫자가 매우 크므로, java에서는 BigInteger를 활용한다.

• n번째에서 전부 뛰었을 때 위치는 다음과 같다.

  이동 횟수	좌표
  1	K
  2	-K
  3	2K
  4	-2K
  5	3K
  6	-4K

  • 위 표에서 알 수 있듯이 이동횟수를 보면, 좌표를 알아낼 수 있다.
  • 이동횟수가 짝수면 음수, 홀수면 양수
  • 좌표의 절댓값

    $$|pos| = K*((n+1)/2)$$

• 만약 남은 거리가 0이라면 n번째에 바라보는 방향으로 종료한다.

• 0이 아니라면, 다음 방향으로 이동한다.
  • n이 짝수라면 n번째에는 오른쪽으로 뛰었으므로 다음(n+1)에는 왼쪽으로 뛰어야한다.
  • n이 홀수라면 n번째에는 왼쪽으로 뛰었으므로 다음(n+1)에는 오른쪽으로 뛰어야한다.
  • 남은 거리를 계산하자
    • n번째 까지 전부 뛸 수 있으면 등차수열의 합을 이용하면 다음과 같다.

      $$\begin{aligned} leftLength &= (N-1)-K\sum_{i=1}^{n}i \\&= (N-1) - K{n(n+1)\over2} \end{aligned}$$

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class java_23631 {
    static int T;
    static int N, K;

    static int findn() {
        int low = 0;
        int high = 5000;

        while (low < high) {
            int mid = (low + high) / 2;

            BigInteger bigInteger = BigInteger.valueOf(mid);
            bigInteger = bigInteger.multiply(BigInteger.valueOf(mid + 1));
            bigInteger = bigInteger.multiply(BigInteger.valueOf(K));

            if (bigInteger.compareTo(BigInteger.valueOf(2 * N)) == -1) {
                low = mid + 1;
                continue;
            }

            high = mid;
            continue;
        }

        return low;
    }

    static String solution() {
        // n(n+1)/2 <= N 인 n의 최댓값 찾기 -> 이분탐색
        // System.out.println("==============");
        int n = findn();
        // System.out.println("findn : " + n);

        // 직전 좌표와 남은 거리 구하기
        // 1. 직전 좌표(절댓값)
        // System.out.println("nowLength" + nowLength);
        // 2. 부호 부여
        int pos = 0;
        // System.out.println("pos " + pos);

        if (n % 2 == 0) {
            pos = -K * ((n + 1) / 2);
            pos -= N - 1 - (n * (n + 1) * K / 2);
            return pos + " L";
            // System.out.println(pos + " L");
        } else {
            pos = K * ((n + 1) / 2);
            pos += N - 1 - (n * (n + 1) * K / 2);
            return pos + " R";
            // System.out.println(pos + " R");
        }

        // 3. 남은 거리 구하기
        // System.out.println("leftLength : " + leftLength);

        //
        // 다음 가야할 방향 구하기

        // 좌표 구하기
        // n이 홀수면 +
        // n이 짝수면 -
        // (kn+1)/2 값
    }

    public static void main(String[] args) throws IOException {
        // N-1 미터를 뛰기
        //
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            // K
            // K*2
            // K*3
            // ...
            // 초기항 K, 등차 K인 등비수열의 합
            //
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            String result = solution();
            bw.write(result + "\n");

        }

        br.close();
        bw.close();
    }
}

---

Uploaded by N2T