[파이썬] [백트래킹] 백준 22251 빌런 호석

문제

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

22251번: 빌런 호석

코드

# 0~9까지의 수를 배열로 표시
array=[[] for _ in range(10)]
array[0]=[1,1,1,0,1,1,1]
array[1]=[0,0,1,0,0,1,0]
array[2]=[1,0,1,1,1,0,1]
array[3]=[1,0,1,1,0,1,1]
array[4]=[0,1,1,1,0,1,0]
array[5]=[1,1,0,1,0,1,1]
array[6]=[1,1,0,1,1,1,1]
array[7]=[1,0,1,0,0,1,0]
array[8]=[1,1,1,1,1,1,1]
array[9]=[1,1,1,1,0,1,1]

# 배열 안의 숫자를 바꿔주는 함수 ex) [3, 5] -> 35
def change(temp):
    length=len(temp)-1
    result_ch=0
    for i in temp:
        result_ch+=i*pow(10,length)
        length-=1
    return result_ch

# on-off 차이가 있는것을 count
def check(ori,com):
    count=0
    for i in range(7):
        if array[ori][i]!=array[com][i]:
            count+=1
    return count

def dfs(index,temp,p):
    global result
    # return 조건
    if index==len(x) and 1 <= change(temp) and change(temp) <= n:
        result+=1
        return
    if index==len(x):
        return
    for i in range(10):
        # 반전 갯수보다 큰경우
        if p-check(x[index],i)>=0:
            p-=check(x[index],i)
            temp.append(i)
            dfs(index+1,temp,p)
            temp.pop()
            p+=check(x[index],i)

n,k,p,x=map(int, input().split())
result=0

x=str(x)
# x=4 , x.zfill(2) -> 04
x=x.zfill(k)
x=[n for n in x]
for i in range(len(x)):
    x[i]=int(x[i])
dfs(0,[],p)

# 문제 조건에서 최소 1개이상 바꾸므로 전체 -1
print(result-1)

어려웠던 부분

1. "1이상"이라는 문제 조건을 잘못 읽어 문제를 해결하는데 시간을 많이 사용하였다.

2. 아무 생각없이 pop대신 remove를 사용하여 문제를 해결하는데 시간을 많이 사용하였다.