[백준/Java] 6523 : 요세푸스 한 번 더!

📌 문제 정보

• 번호: 6523
• 제목: 요세푸스 한 번 더!
• 난이도: Gold 2
• 분류: 구현, 자료구조, 해시

---

💡 접근 방식

ax²+b mod N 점화식으로 다음 사람을 선택하는 게임에서 술을 마시지 않는 사람의 수를 구하는 문제입니다.
처음에는 HashMap으로 방문 횟수를 관리했으나 메모리 초과가 났고,
플로이드 순환 찾기 알고리즘(토끼와 거북이)으로 다시 풀었습니다.

---

🔹 1단계 – HashMap 접근 (메모리 초과)

HashMap은 엔트리당 약 80 bytes의 객체 오버헤드가 있어서
최대 2×10^6 엔트리 × 80 bytes = 160MB → 메모리 제한 128MB 초과

---

🔹 2단계 – 플로이드 순환 찾기 알고리즘

수열 구조:

0 → x₁ → x₂ → ... → 입구 → ... → 입구 (순환)
      ↑ 고리 밖 (L명)  ↑    고리 안 (C명)

• 고리 밖 사람들 → 딱 1번만 호출 → 술 안 마심
• 고리 안 사람들 → 반드시 2번 호출 → 술 마심
• 답 = N - 고리 길이(C)

---

🔹 3단계 – 알고리즘 3단계

1단계: 순환 고리 안으로 진입

long tortoise = next(0, a, b, N);
long hare = next(next(0, a, b, N), a, b, N);

while (tortoise != hare) {
    tortoise = next(tortoise, a, b, N);
    hare = next(next(hare, a, b, N), a, b, N);
}

2단계: 순환 입구 찾기

tortoise = 0;
while (tortoise != hare) {
    tortoise = next(tortoise, a, b, N);
    hare = next(hare, a, b, N);
}

3단계: 고리 길이 측정

long cycleLength = 1;
long current = next(tortoise, a, b, N);
while (current != tortoise) {
    current = next(current, a, b, N);
    cycleLength++;
}

---

💻 핵심 수학 원리

L: 시작점 → 순환 입구까지 거리
C: 순환 고리 길이
d: 순환 입구 → 첫 만남 지점까지 거리

L + d = nC  →  L = nC - d

거북이를 0으로 보내면
  거북이: L만큼 이동 → 입구 도착
  토끼:   nC-d만큼 이동 → 입구 도착
→ 둘이 정확히 입구에서 만남

---

💻 핵심 코드

static long next(long x, long a, long b, long N) {
    long x2 = (x * x) % N;
    long ax2 = (a * x2) % N;
    return (ax2 + b) % N;
}

중간마다 % N 을 해줘야 오버플로우 방지

---

⏳ 복잡도 분석

• 시간 복잡도: O(L + C)
• 공간 복잡도: O(1)

---

📄 전체 코드

package B6523;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while (true) {
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line);
            long N = Long.parseLong(st.nextToken());

            if (N == 0) break;

            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());

            long tortoise = next(0, a, b, N);
            long hare = next(next(0, a, b, N), a, b, N);

            while (tortoise != hare) {
                tortoise = next(tortoise, a, b, N);
                hare = next(next(hare, a, b, N), a, b, N);
            }

            tortoise = 0;
            while (tortoise != hare) {
                tortoise = next(tortoise, a, b, N);
                hare = next(hare, a, b, N);
            }

            long cycleLength = 1;
            long current = next(tortoise, a, b, N);
            while (current != tortoise) {
                current = next(current, a, b, N);
                cycleLength++;
            }

            sb.append(N - cycleLength).append("\n");
        }
        System.out.print(sb);
    }

    static long next(long x, long a, long b, long N) {
        long x2 = (x * x) % N;
        long ax2 = (a * x2) % N;
        return (ax2 + b) % N;
    }
}