[Silver III] 1 빼기 - 25709 (python)

문제 링크

성능 요약

메모리: 31120 KB, 시간: 44 ms

분류

그리디 알고리즘, 구현

 

문제 설명

민겸이는 1 빼기를 할 수 있는 능력을 가지고 있다. 1 빼기란, 다음의 두 연산 중 하나를 골라 수행하는 것이다.

1. 가지고 있는 수에서 1을 뺀다.
2. 가지고 있는 수에 있는 1을 하나 지운다. 지우고 난 뒤 좌우의 수들을 순서대로 다시 합쳐 하나의 수로 만든다. 이때 맨 앞의 연속되는 0은 지워진다.

민겸이가 최초로 가지고 있는 정수가 하나 주어질 때, 이 수를 0으로 만들기 위해 최소 몇 번의 1 빼기가 필요한지 구해보자.

입력

민겸이가 가지고 있는 정수 N이 주어진다.

출력

민겸이가 해당 수를 0으로 만들기 위해서 최소 몇 번의 1 빼기가 필요한지 출력한다.

 

 

코드

 

n = int(input())
ans = 0

while n:
    s = str(n)
    ans += s.count('1')
    n = int('0' + s.replace('1', ''))

    if n:
        n -= 1
        ans += 1

print(ans)

방법 - 1을 빼는 것보다 1을 지우는 것이 더 빠르게 할 수 있다. 

주의할 점 

n = int('0' + s.replace('1', '')) 빈문자열을 형변환시 오류 발생