글 읽기 - [Python] 75% 부근에서 자꾸 틀립니다 살려주세요

flame623 3년 전 0

알고리즘은

1)100에서 +-로만 이동하는 횟수

2)내가 갈 채널 n과 같은 자릿수에서 찾는 알고리즘

3)내가 갈 채널 n보다 1큰 자릿수에서 찾는 알고리즘

4)내가 갈 채널 n보다 1 작은 자릿수에서 찾는 알고리즘

이렇게 4파트로 짜고 각 파트의 결과값중 가장 작은 값을 출력하는 형태로 만들었습니다.

처음에는 15%에서 끊기더니 게시판 반례를 전부 다 넣으면서 75%까지 왔는데 더이상 게시판에서는 작동하는 반례도 없고 저도 이것저것 생각을 해 보았으나 진전이 되지 않습니다... 살려주세요 ㅠㅠㅠ

n = input()
k = int(input())
D = list(map(int,input().split())) if k !=0 else []
A = [i for i in range(10) if i not in D]
Len = len(n)

ans1 = abs(int(n)-100)
ans2 = 0

for k in range(Len):
    sub = [0 for i in range(len(A))]
    for i in range(len(A)):
        standard = int(n[:k+1])*10**(Len-k-1)
        sub[i] = abs(standard - ans2 - A[i]*10**(Len-k-1))
        #print("search",ans2 + A[i]*10**(Len-k-1))
        #print("sub", sub[i])
        
    if len(A) != 0:
        find = min(sub)
        possible = [A[i] for i in range(len(sub)) if sub[i] == find]
        poss_sub = [0 for i in range(len(possible))]
        for i in range(len(poss_sub)):
            poss_sub[i] = abs(int(n) - (ans2 + possible[i]* 10**(Len-k-1)))
            #print(ans2 + possible[i]* 10**(Len-k-1))
        ans2 += possible[poss_sub.index(min(poss_sub))] * 10**(Len-k-1)
        #print("ans",ans2)
        #print("")
    
ans2 = abs(int(n) - ans2) + len(str(ans2)) if len(A) !=0 else 100000000000000

ans3 = 0
sub = [0 for i in range(len(A))]

for k in range(Len+1):
    for i in range(len(A)):
        standard = int(n)
        sub[i] = abs(standard - ans3 - A[i]*10**(Len-k))
        #print("search",ans3 + A[i]*10**(Len-k))
        #print("sub", sub[i])
    if len(A) != 0:
        ans3 += A[sub.index(min(sub))] * 10**(Len-k)
        #print("ans",ans3)
        #print("")

ans3 = abs(int(n) - ans3) + len(str(ans3)) if len(A) !=0 else 100000000000000

ans4 = 0 if Len-1 !=0 else 100000000000000
sub = [0 for i in range(len(A))]
for k in range(Len-1):
    for i in range(len(A)):
        standard = int(n)
        sub[i] = abs(standard - ans4 - A[i]*10**(Len-2-k))
        #print("search", ans4 + A[i]*10**(Len-2-k))
        #print("sub", sub[i])
    if len(A) != 0:
        ans4 += A[sub.index(min(sub))] * 10**(Len-2-k)
        #print("ans",ans4)
        #print("")

ans4 = abs(int(n) - ans4) + len(str(ans4)) if len(A) !=0 else 100000000000000

print(min(ans1, ans2, ans3, ans4))
#print(ans1, ans2, ans3, ans4)

rlasshi 3년 전 0

제가 돌려봤을 때
500000
2
1 5
를 인풋하면 7이 나오네요...
자릿수로 접근하면 세부적인 경우의 수가 너무 많아지므로 좀 더 일반화된 형식으로 접근하시면 좋을 것 같습니다!

severck12 3년 전 4

500000

1 5

하면 7이 나오는게 맞는거 아닌가요..?

kangbk4188 2년 전 0

7나오는게 맞는거 같네요..

sinusoid500 1년 전 0

저도 파이썬으로 질문 작성자님과 같은 알고리즘으로 짰는데 동일하고 75%에서 틀리고 있습니다.

다른 게시판의 모든 반례들도 잘 풀리고 있고요.

혹시 해결하셨나요?

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

문제

문제

출처

ICPC

[Python] 75% 부근에서 자꾸 틀립니다 살려주세요

flame623 3년 전 0

rlasshi 3년 전 0

severck12 3년 전 4

kangbk4188 2년 전 0

sinusoid500 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말