[프로그래머스] 점프와 순간이동

1. 생각의 흐름

처음 문제를 봤을 때 탐욕 알고리즘을 사용해야하나 싶었다.

맨 처음 한 칸은 무조건 JUMP로 가고, 목표보다 작은 최대값을 가질 때까지 TP하고 나머지는 JUMP하면 되려나? 라고 생각했다.

그런데 뭔가 좀 이상했다. 간단하게 생각해봐도 이는 최적해를 도출할 수 없을 것 같았다.

2배를 간다고 했으므로…

1. 처음 한칸만 JUMP : 1 → 2 → 4 → 8 → 16 …

2. 세 칸 JUMP : 3 → 6 → 12 → 24 → 48 …

여기서 만약에 가야하는 목표 거리가 21이라고 생각해 본다면 첫 번째 방법은 JUMP를 7번, 2번째 방법은 JUMP를 3번한다.

따라서 탐욕 알고리즘을 버리고 그냥 간단하게 생각해보기로 했다.

---

n이 짝수라면 다음과 같고

• n 일 때 사용한 건전지량 == n / 2 일때 사용한 건전지량

n이 홀수라면 다음과 같다.

• n 일 때 사용한 건전지량 == (n-1) / 2일때 사용한 건전지량 + 1

결국 반복문으로 간단하게 돌려주면 해결할 수 있는 쉬운 문제였다.

2. 코드 구현

def solution(n) :
    count = 0
    
    while n > 0 :
        if n % 2 != 0 :
            count += 1
            n -= 1
        n //= 2
    return count

solution(5000)

5