백준 3165 5 Python

🐸 문제 정보

3165번: 5

 

🤖 알고리즘

그리디

백트래킹

 

⏱️ 풀이 시간

60m+

 

📝 풀이

사실 완벽하게 풀이하지 못한 문제이다.

질문이 엄청 깔끔하고, 이해하기 쉬운 반면... 정말 엄청나게 틀렸다.

사실 아직까지 틀린 이유를 모르겠다.

 

기존에 풀이 방식은 아래와 같았다.

(num은 n + 1을 리스트로 바꾼 변수, idx는 -1)

1. 백트래킹 함수 내에서 5가 k개 이상이면 멈추도록 함
2. num[idx]가 5라면 백트래킹 함수를 재귀하는데, idx 값을 -1 해줌
   • 자리수를 넘겨주기 위해서
3. num[idx]가 5보다 작은 경우, 5로 만들고 idx 값을 -1 하여 재귀
4. num[idx]가 5보다 큰 경우, 5로 만들되 idx값을 그대로 재귀
   • 만약 자리수가 아예 하나 늘어나 버린 경우까지 커버하기 위해서

틀린 답

import sys
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())
num = list(str(n + 1))

def bt(idx):
    global num
    if num.count('5') >= k:
        return
    if (num[idx] == '5') and (abs(idx) < len(num)):
        bt(idx - 1)
    else:
        if int(num[idx]) < 5:
            num[idx] = '5'
        else:
            num[idx] = '5'
            temp = int(''.join(num)) + (10 ** abs(idx))
            num = list(str(temp))
        bt(idx)

bt(-1)
print(int(''.join(num)))

이렇게 풀어도 제안된 테케와, 내 머리 속에서 나온 반례는 전부 통과했으나 26%를 넘어가지 못했다.

여기서 어떤식으로 변형해봐도 절대절대 26%를 뚫을 수 없었고... 결국 검색을 통해 아이디어를 찾았다.

 

아이디어 자체는 위 플로우와 크게 상이한 점이 없었다.

굳이 다른 점을 찾자면... 자리 수의 값을 1씩 더해주면서 5를 만들었다는 점...?

이 부분에서 왜 정답 유무가 달라지는지는 잘 모르겠다. 애초에 푼 사람이 별로 없는 문제라 반례를 더 찾을 수도 없었다.

 

고친 답이 이해가 안되거나 모르겠는 것은 아니지만... 기존 답이 왜 틀렸는지는 머리를 조금 환기하고 다시 생각해봐야겠다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())
num = list(str(n + 1))
ml = len(num)
idx = -1

while True:
    if num.count('5') >= k:
        break
    while (num[idx] == '5') and (abs(idx) < ml):
        idx -= 1
    temp = int(''.join(num)) + (10 ** (abs(idx) - 1))
    num = list(str(temp))
    ml = len(num)

print(int(''.join(num)))