문제

https://programmers.co.kr/learn/courses/30/lessons/12980

나의 코드 (답안참조)

"""
1. 아이디어

2. 시간복잡도

"""

def solution(n):
    ans = 0
    
    while n > 0:
        
        if n % 2 == 0:
            n //= 2
        
        else:
            ans += 1
            n -= 1

    return ans
    

설명

백준에 숨바꼭질 문제가 생각나서 bfs를 생각하긴 했는데 n의 범위를 보니깐 단순 반복문을 써야 하는것 같았다.

증가 패턴 공식은 알았는데 짝수 홀수 까진 생각을 못해서 못풀었다..

이게 힌트임

5000 -> 2500
2500 -> 1250
1250 -> 625
625 -> 624 + 1(ans++)
624 -> 312
312 -> 156
156 -> 78
78 -> 39
39 -> 38 + 1(ans++)
38 -> 19
19 -> 18 +1(ans++)
18 -> 9
9 -> 8 + 1(ans++)
8 -> 4
4 -> 2
2 -> 1
1 -> 0 + 1(ans++)
0

참고자료