[백준] 30178: Perfect Triples (Java, Python)

Perfect Triples

Codeforces 비트마스킹 수학 패턴 Python Java

문제 분석

• 무한 수열 s가 있고, 연속된 세 원소 (a, b, c)가 트리플을 이룬다
• 트리플 조건: a, b, c는 서로 다르고, a ⊕ b ⊕ c = 0이며, a < b < c
• 트리플은 사전순(lexicographic)으로 가장 작은 것부터 순서대로 나열
• n이 주어지면 s(n)을 출력 (1-indexed)
• 제약: T ≤ 10⁴, n ≤ 10¹⁸

접근법

• 핵심 관찰: 트리플들은 그룹 단위로 구성된다
• 그룹 k (k=0,1,2,...): 4^k개의 트리플을 포함, a ∈ [4^k, 2·4^k − 1]
• 그룹 k의 수열 원소 수: 3 × 4^k개
• 2비트 청크 매핑: a의 각 2비트 청크로부터 b, c의 대응 비트를 결정

2비트 매핑 규칙 (a → b, c):

• 00 → (00, 00)
• 01 → (10, 11)
• 10 → (11, 01)
• 11 → (01, 10)

이 매핑은 a ⊕ b ⊕ c = 0을 만족하면서 a < b < c를 보장한다.

알고리즘: n이 주어지면 → 그룹 k 찾기 (pw = 4^k) → 그룹 내 오프셋 m 계산 → a = pw + m/3 → m%3으로 a/b/c 중 어떤 값인지 결정 → 2비트 매핑으로 b, c 계산

풀이 (Python)

import sys
input = sys.stdin.readline

def solve(n):
    # 그룹 k 찾기: 그룹 k는 3*4^k개의 원소를 가짐
    pw = 1
    while pw * 4 <= n:
        pw *= 4
    # pw = 4^k, 그룹 내 오프셋
    m = n - pw
    a = pw + m // 3       # 트리플의 첫 번째 값
    pos = m % 3           # 0=a, 1=b, 2=c
    if pos == 0:
        return a
    # 2비트 청크 매핑으로 b, c 계산
    b = c = 0
    s = 0
    tmp = a
    while tmp:
        bits = tmp & 3
        if   bits == 1: bb, cc = 2, 3
        elif bits == 2: bb, cc = 3, 1
        elif bits == 3: bb, cc = 1, 2
        else:           bb, cc = 0, 0
        b |= bb << s
        c |= cc << s
        tmp >>= 2
        s += 2
    return b if pos == 1 else c

t = int(input())
out = []
for _ in range(t):
    out.append(str(solve(int(input()))))
sys.stdout.write('\n'.join(out))

풀이 (Java)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine().trim());
            // 그룹 k 찾기
            long pw = 1;
            while (pw * 4 <= n) pw *= 4;
            long m = n - pw;
            long a = pw + m / 3;
            int pos = (int)(m % 3);
            if (pos == 0) { sb.append(a).append('\n'); continue; }
            // 2비트 청크 매핑
            long b = 0, c = 0, tmp = a;
            for (int s = 0; tmp > 0; s += 2, tmp >>= 2) {
                int bits = (int)(tmp & 3);
                int bb, cc;
                if      (bits == 1) { bb = 2; cc = 3; }
                else if (bits == 2) { bb = 3; cc = 1; }
                else if (bits == 3) { bb = 1; cc = 2; }
                else                { bb = 0; cc = 0; }
                b |= (long)bb << s;
                c |= (long)cc << s;
            }
            sb.append(pos == 1 ? b : c).append('\n');
        }
        System.out.print(sb);
    }
}

예제 트레이스

n = 9  (그룹 1의 마지막 원소)

pw = 4 (4^1 = 4, 4*4=16 > 9이므로 stop)
m = 9 - 4 = 5
a = 4 + 5/3 = 4 + 1 = 5 = 101(2)
pos = 5 % 3 = 2  → c를 출력

a = 5 = 01|01(2비트 청크)
  청크 01 → bb=2(10), cc=3(11)
  청크 01 → bb=2(10), cc=3(11)

b = 10|10(2) = 10
c = 11|11(2) = 15

pos=2이므로 c = 15 출력

수열 확인: s = [1,2,3, 4,8,12, 5,10,15, 6,11,13, 7,9,14, ...]
s(9) = 15 ✓

시간 복잡도

O(T log N)

공간 복잡도

O(1)

알고리즘 풀이 블로그