[백준22251/골5] 빌런 호석 - Python

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

 

 

문제의 이미지 보고 비트연산으로 풀어야겠다고 생각했다.

근데 비트연산 제대로 써본적이 없음... 일단 비트 연산자 먼저 공부했다.

 

 

1. 껐다켰다 할 수 있는 LED는 총 7개 -> 7자리 이진수로 변환하여 나타냄

2. 1부터 N까지의 수를 하나씩 순회 -> 현재 K층의 숫자에서 몇개의 LED를 바꿔야하는지 계산 (XOR 연산)

3. 바꾼 LED를 세서 P개 이하라면 result += 1

 

 

실패 코드

# python 시간초과, pypy 2068ms

LED = {
    "0": '1110111',
    "1": '0010010',
    "2": '1011101',
    "3": '1011011',
    "4": '0111010',
    "5": '1101011',
    "6": '1101111',
    "7": '1010010',
    "8": '1111111',
    "9": '1111011'
}

N, K, P, X = map(int, input().split())

result = 0

for i in range(1, N+1):
    floor = '0' * (K - len(str(i))) + str(i)
    current = '0' * (K - len(str(X))) + str(X)
    total_change = 0

    if i == X:
        continue

    for j in range(K):
        change = format(int(LED[floor[j]], 2) ^ int(LED[current[j]], 2), '07b').count("1")
        total_change += change

        if total_change > P:
            break

    if total_change <= P:
        result += 1

print(result)

 

원인 : 비트를 문자열로 나타내서 더 오래걸림

 

 

성공 코드

# python 32544KB 3020ms, pypy 111496KB 1516ms
# 1~N 사이의 숫자로 바꾸기, K자리수, 최대 P개의 LED 반전, 실제 X층에 서있음
# 각 LED 번호 비트로 변환
# 각 자릿수 순회하면서 바꿔야하는 LED 수 구하고, P개 이하이면서 N이하의 수일 경우에 += 1

LED = {
    "0": 0b1110111,
    "1": 0b0010010,
    "2": 0b1011101,
    "3": 0b1011011,
    "4": 0b0111010,
    "5": 0b1101011,
    "6": 0b1101111,
    "7": 0b1010010,
    "8": 0b1111111,
    "9": 0b1111011
}

N, K, P, X = map(int, input().split())

result = 0
current = '0' * (K - len(str(X))) + str(X)

for i in range(1, N+1):
    floor = '0' * (K - len(str(i))) + str(i)
    total_change = 0

    if i == X:
        continue

    for j in range(K):
        change = bin(LED[floor[j]] ^ LED[current[j]]).count('1')
        total_change += change

        if total_change > P:
            break

    if total_change <= P:
        result += 1

print(result)

 

 

이진수로 표현하니까 성공했다.