[Level 2] 점프와 순간이동

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

코딩테스트 연습 - 점프와 순간 이동

---

접근

DP로 접근을 해보았다. 이전위치에서+1과 비교를 하는데 현재위치가 짝수일 때는 현재위치/2의 사용량과 비교를 하고 홀 수 일때는 현재위치/2 +1과 비교를 한다. 점화식을 세워보면 다음과 같다.

짝수일 때

DP[i] = DP[i-1]+1 or DP[i/2]

홀수일 때

DP[i] = DP[i-1]+1 or DP[i/2]+1

하지만 테스트케이스는 모두 통과했지만 효율성에서 모두 시간초과가 발생했다.

 

그래서 다른 사람들의 풀이를 참고하였다.

역순인 N부터 0까지 이동을 한다. 건전지를 최소로 사용해야하고 -> 최소로 사용하기 위해서는 점프를 최소, 순간 이동을 최대로 해야한다. 따라서 N부터 2로 나누다가 나머지가 발생했을 때는 점프를 한다.

여기서 N을 이진수로 변환하면 1의 개수가 건전지 사용량이 된다.

 

구현

입력받은 n을 이진수로 변환하고 1의 개수를 ans에 대입하여 반환한다.

 

처음에 DP를 생각하고 시간초과가 발생했을 때 다른 풀이도 생각을 해봤어야했다. 

최적해를 구하는 문제에서는 어떻게 해야 최적이 될까를 생각해보면서 발전시켜 나간다.

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