프로그래머스 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과

# Greedy 문제임을 직감했지만 구현하지 못함

수를 더하거나 2배씩 늘려 목표한 n값을 도출하는 문제입니다. 수의 패턴이 그려지지 않아 구현하지 못하여 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(n):

    ans = 0
    
    while n!=0:
        if n%2==0:
            n/=2
        else:
            ans+=1
            n-=1
            
    return ans

생각보다 간단한 풀이로 구현할 수 있었습니다. 주어진 수 n을 2나누며 나누어 떨어지지 않을 때는 -1씩 하여 다시 2로 나누는 방식입니다. 풀이 시 1일때는 점프+1, 2일때는 점프+1와2배로 생각하였는데 문제에서 주어진 입력/출력 예시 5000/5를 보고 거꾸로 5000,2500,1250.. 으로 나누어보면 생각하였다면 쉽게 풀 수 있지 않았을까 생각하였습니다.

[다른 사람의 풀이2]

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

또 다른 풀이로 이진법을 활용한 풀이입니다. 문제에서 묘사하는 점프와 2배 순간이동은 사실 이진법에서 +1하거나 2배하여 자릿수를 올리는 원리와 같았습니다. 그리하여 주어진 n을 이진수로 바꾸고 1의 갯수만 파악하면 되는 문제였습니다.

감사합니다.