[백준][Python] 22251 빌런 호석

구현, 브루트포스 / 골드 5

🛗

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

22251번: 빌런 호석

 

 

내 풀이

def onoff(nX):
    global result
    ans = 0
    
    if nX < 1 or nX > N:
        return
    
    currentX = list(f'{X:0{K}d}')
    currentnX = list(f'{nX:0{K}d}')

    for i in range(K):
        currentXNum = num[currentX[i]].copy()
        currentnXNum = num[currentnX[i]].copy()
        common_values = [value for value in currentXNum if value in currentnXNum]
        final = [x for x in currentXNum + currentnXNum if x not in common_values]

        ans += len(final)

    if 0 < ans <= P:
        result += 1

# N: 최대 층수, K: 자리 수, P: 최대 반전 가능 수, X: 현재 층수
N, K, P, X = map(int, input().split())
num = {'0': [1,2,3,5,6,7], '1': [3,6], '2': [1,3,4,5,7], '3': [1,3,4,6,7], '4': [2,3,4,6], '5': [1,2,4,6,7], '6': [1,2,4,5,6,7], '7': [1,3,6], '8': [1,2,3,4,5,6,7], '9': [1,2,3,4,6,7]}
result = 0

for n in range(1, N+1):
    onoff(n) # 변경 대상 층수

print(result)

 

 

 

코드 설명

 

N: 엘리베이터의 최대 층수

K: 층수를 보여주는 디스플레이 자리 수

P: 최대 반전 가능 개수

X: 현재 층수

num: key = 0~9까지의 숫자를 나타내는 문자, value = 각 숫자를 표시하기 위해 들어와야 하는 표시등 위치 리스트

result: 정답 변수(엘리베이터 LED를 올바르게 반전시킬 수 있는 경우의 수)

N, K, P, X = map(int, input().split())
num = {'0': [1,2,3,5,6,7], '1': [3,6], '2': [1,3,4,5,7], '3': [1,3,4,6,7], '4': [2,3,4,6], '5': [1,2,4,6,7], '6': [1,2,4,5,6,7], '7': [1,3,6], '8': [1,2,3,4,5,6,7], '9': [1,2,3,4,6,7]}
result = 0

다음과 같이 숫자를 매겨서 생각했다.

 

1부터 N까지 가능한 모든 층수를 onoff 함수의 매개변수로 전달하며 검사하였다.

for n in range(1, N+1):
    onoff(n) # 변경 대상 층수

 

 

✔️ onoff 함수

 

전역변수 result 사용.

ans: 현재 층수(X)에서 목표 층수(nX)까지 반전되어야 하는 총 개수

global result
ans = 0

 

currentX: 현재 층수(X)를 K자리 숫자로 표현한 후, 리스트로 변환

currentnX: 목표 층수(nX)를 K자리 숫자로 표현한 후, 리스트로 변환

부족한 자리는 0으로 채워진다.

currentX = list(f'{X:0{K}d}')
currentnX = list(f'{nX:0{K}d}')

 

모든 자릿수(K)를 돌며 검사한다.

 

currentXNum: 현재 층수(X)의 현재 자릿수(i)를 표시하기 위해 들어와야 하는 표시등 위치 리스트 복사본

currentnXNum: 목표 층수(nX)의 현재 자리수(i)를 표시하기 위해 들어와야 하는 표시등 위치 리스트 복사본

원본 값이 변경되면 안 되기 때문에 copy()해서 사용했다.

 

common_values: 두 리스트 간 겹치는 표시등 위치 리스트

final: 두 리스트를 합치되, 겹치는 표시등을 제외하고 합쳐준다.

 

ans는 final의 길이가 된다.

 

직접 써보면서 생각하다가 문제 해결 방식을 찾아냈다.

for i in range(K):
    currentXNum = num[currentX[i]].copy()
    currentnXNum = num[currentnX[i]].copy()
    common_values = [value for value in currentXNum if value in currentnXNum]
    final = [x for x in currentXNum + currentnXNum if x not in common_values]

    ans += len(final)

 

for문이 끝나고, ans(반전되어야 하는 개수)가 0보다 크고 P보다 작거나 같다면 정답 변수의 값을 1 증가시킨다.

여기서 0보다 커야 하는 이유는, X와 nX가 같은 숫자인 경우를 방지하기 위해서이다.

if 0 < ans <= P:
    result += 1

 

 

 

🙀 어려웠던 점

 

시간초과, 메모리 초과가 발생했다.

처음에는 onoff()에서 이중 for문을 사용했었는데, 삭제해 주니 PyPy3로는 잘 돌아간다.

 

수정 전 코드

# 이중 for문 사용
for i in range(K):
    currentXNum = num[currentX[i]].copy()
    currentnXNum = num[currentnX[i]].copy()
    common_values = [value for value in currentXNum if value in currentnXNum]

    for value in common_values:
        if value in currentXNum:
            currentXNum.remove(value)
        if value in currentnXNum:
            currentnXNum.remove(value)

    ans += len(currentXNum + currentnXNum)

 

수정 후

for i in range(K):
    currentXNum = num[currentX[i]].copy()
    currentnXNum = num[currentnX[i]].copy()
    common_values = [value for value in currentXNum if value in currentnXNum]
    final = [x for x in currentXNum + currentnXNum if x not in common_values]

    ans += len(final)