글 읽기 - [python] 1170 리모컨.. dfs 조언 혹은 반례부탁드립니다.

jaa7963 2년 전 0

안녕하세요.

반복문 형식으로 풀어봐서

반복문으로 풀 수 있으면, 재귀함수로도 풀 수 있을 것 같아

dfs로 도전해보았습니다.

저의 접근방식에 대한 설명은 주석에 덧붙여놓았습니다.

반례도 제가 게시판에서 찾아서 대입해 볼 수 있을 만큼은 넣어본것 같습니다.

부족한 실력이라 코드를 보기가 번거롭겠지만,

어떤식으로 수정해야할지 조언 또는 반례 부탁드리겠습니다..

n=int(input())
num=len(str(n))
broken_number=int(input())


if broken_number==0:
    broken_list=[]
else:
    broken_list=list(map(int,input().split()))

# 일단 0~9 까지 다 받았습니다.
not_broken=[n for n in range (0,10)]

# 고장난 버튼을 제외했습니다.
for x in broken_list:
    not_broken.remove(x)

# 스트링형식으로 만들어서 dfs 시에 한 글자씩 붙이려고 str 함수를 적용해보았습니다.
not_broken=list(map(str,not_broken))
res=2147000000
        
def dfs(v,string):
    global res,not_broken

    if v==num:
        
        #string의 글자수가 목표 채널의 자릿수와 같아지면, 갱신해주었습니다. 
        
        deviation=abs(int(string)-n)
        
        if deviation<res:
            res=deviation
        return

    else:
        # 고장나지 않은 버튼들로만 조합을 만들었습니다.
        for extra in not_broken:
            dfs(v+1,string+extra)
            
dfs(0,"")

print(min(res+num,abs(100-n)))

kangwh0617 2년 전 5

아래와 같은 반례가 있네여

9
9
0 2 3 4 5 6 7 8 9


Output:9
Answer:4
(11--)

jaa7963 2년 전 0

도와주셔서 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python] 1170 리모컨.. dfs 조언 혹은 반례부탁드립니다.

jaa7963 2년 전 0

kangwh0617 2년 전 5

jaa7963 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말