[Python/파이썬] Summer/Winter Coding(~2018) 점프와 순간 이동

프로그래머스

코드

def solution(n):
    answer = 0
    while True:
        if n == 0:
            return answer
        elif n == 1:
            return answer + 1
        else:
            while n % 2 == 0:
                n //= 2
            n -= 1
            answer += 1

처음에는 dp로 풀었다가 효율성 0점 맞고 다시 위의 코드로 풀었더니 통과했다...

아래의 코드가 효율성 0점 맞은 DP 풀이ㅠ정확성은 다 통과하긴 했다. N이 10억까지 나와서 dp로 풀면 안된다.

def solution(n):
    ans = 0
    dp = [int(1e9) for _ in range(n+1)]
    dp[0], dp[1] = 0, 1
    
    for i in range(2, n+1):
        if i % 2 == 0:
            dp[i] = dp[i // 2]
        else:
            dp[i] = dp[i-1] + 1
    return dp[n]

근데 다 풀고 다른 사람들 풀이를 보니 정말 짧게 풀었는데 또 처음보는 함수 나왔다.

def solution(n):
    return bin(n).count('1')

bin() 함수는 10진수를 2진수로 바꾸어주는 함수이다. 주어진 n을 2진수로 바꾸고 1의 개수를 세어주면 쉽게 풀 수 있는 문제였다...