[백준] 3165 5

문제

• N과 K가 주어졌을 때, N보다 크면서 5가 적어도 K번 포함되는 가장 작은 수 구하기
• 1 <= N <= 10^15
  1 <= K <= 15
  
  

 

풀이

• 뒤에서부터 확인해서 5가 아닌 수가 나오면 +1 하면서 5가 K개가 되는 숫자 찾기
• 리스트 형태가 아니라 문자열 형태로 동일한 코드를 작성했는데 '시간 초과' 나왔다. 

 

N, K = map(int,input().split())
N = list(str(N+1))
cur_idx = -1       # 현재 인덱스
max_idx = len(N)   # 최대 인덱스

while True:
    if N.count('5') >= K:
        break

    # 5가 아닌 인덱스 찾기
    while N[cur_idx] == '5' and abs(cur_idx) < max_idx:
        cur_idx -= 1
    
    # 5가 아닌 인덱스 +1 하기
    N = list(str(int(''.join(N)) + 10**(abs(cur_idx)-1)))
    # 최대 인덱스 재설정
    max_idx = len(N)
 
print(''.join(N))

 

References

• 백준 오늘의 문제
• https://welog.tistory.com/296