22251번: 빌런 호석(파이썬)

💡 문제 요약

• 1부터 N까지의 번호를 K자리 7-세그먼트 디스플레이로 표현
• 현재 표시된 페이지 X에서 최대 P번의 세그먼트 스위치(on↔off)로 이동 가능한 다른 페이지 수를 구하라
• 단, X 자신은 제외

 

🧠 문제 배경

7-세그먼트 디스플레이는 다음 7개 선분(세그먼트) 조합으로 숫자를 표시한다:

   --0--     ← 상단
  |     |
 5|     |1   ← 좌/우 상단
  |     |
   --6--     ← 중앙
  |     |
 4|     |2   ← 좌/우 하단
  |     |
   --3--     ← 하단

• 각 숫자(0~9)는 고유의 세그먼트 켜짐/꺼짐 패턴을 가짐
• 한 숫자에서 다른 숫자로 바꿀 때, 켜거나 꺼야 할 세그먼트 수 = 스위치 비용
• 스위치 비용 합이 P 이하인 경우에만 이동 가능

 

🔍 알고리즘 설계

1️⃣ 세그먼트 패턴 정의

# 0~9 각각 7개 세그먼트 on(1)/off(0) 배열
segment_map = {
    0: [1,1,1,1,1,1,0], 1: [0,1,1,0,0,0,0],
    2: [1,1,0,1,1,0,1], 3: [1,1,1,1,0,0,1],
    4: [0,1,1,0,0,1,1], 5: [1,0,1,1,0,1,1],
    6: [1,0,1,1,1,1,1], 7: [1,1,1,0,0,0,0],
    8: [1,1,1,1,1,1,1], 9: [1,1,1,1,0,1,1]
}

2️⃣ 스위치 비용 테이블 구축

• 모든 숫자 쌍 (a, b)에 대해 7개 세그먼트 비교
• 다를 때마다 +1
• O(10×10×7) = 700회 연산 (상수 시간)

# switch_map[a][b] = a→b 전환 스위치 횟수
switch_map = [[0]*10 for _ in range(10)]
for a in range(10):
    for b in range(10):
        cost = 0
        for seg in range(7):
            if segment_map[a][seg] != segment_map[b][seg]:
                cost += 1
        switch_map[a][b] = cost

3️⃣ 후보 페이지 비교

• 1부터 N까지 순회 (X 제외)
• 각 수 num을 str(num).zfill(K)로 K자리 문자열화
• 각 자리 i에서 switch_map[x_i][num_i] 합산
• 합이 P 이하이면 이동 가능 → 카운트++

n, k, p, x = map(int, input().split())
x_str = str(x).zfill(k)
ans = 0
for num in range(1, n+1):
    if num == x:
        continue
    s = str(num).zfill(k)
    total = 0
    for xi, yi in zip(x_str, s):
        total += switch_map[int(xi)][int(yi)]
        if total > p:
            break
    else:
        ans += 1
print(ans)

 

 

✅ 시간 복잡도 분석

단계	연산량	복잡도
세그먼트 패턴 정의	상수	O(1)
스위치 테이블 구축	700회	O(1)
후보 페이지 비교	N × K × O(1)	O(N·K)

• 최대 N, K ≤ 1,000이라면 N·K ≤ 10⁶ → 충분히 빠름

---

📌 정리

• 7-세그먼트 디스플레이 전환은 자리별 스위치 비용을 미리 계산해두면 빠름
• 정렬, 탐색 없이 O(N·K) 로 모든 후보를 검사 가능
• K자리 표시와 스위치 최대 횟수 P 제약을 고려하여 효율적으로 구현할 수 있다