[Summer/Winter Coding(~2018) / 프로그래머스] 12980번 : 점프와 순간이동

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

 

Lv2 문제고, 스스로 푼 문제다!

 

문제 이해

최종 목적지까지 최소한의 건전지로 가려면 순간이동을 최대한 많이 활용해야 한다.

목적지부터 거슬러 올라가면 짝수인 수는 짝수 // 2인 수에서 순간이동을 하면 되므로 상관 없고, 문제는 홀수인 지점에서는 홀수 - 1까지는 순간이동하고 홀수 - 1에서 한칸만 이동하면된다 

 

1. n이 짝수라면 n을 n // 2로 이동시키면 된다

2. n이 홀수라면 n -= 1을 한 다음 사용한 건전지를 count에 +1해주면 된다

3. n == 1일 때는 0에서 한칸 움직이면 되므로 count += 1을 해주고 break한다 

 

 

- 정답 풀이 :

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

 

- 시도한 풀이 

정확성은 다 맞았는데, 효율성에서는 다 틀린 문제다 (1억 이상의 수에 대해서는 시간초과가 발생하는 것 같다)

이전에 계산한 걸 다시 사용하는 것 같아 dp로 풀었는데 큰 수에 대해서는 시간초과가 발생하는 풀이인 것 같다

def solution(n):
    dp = [0, 1, 1]
    
    for i in range(3, n + 1):
        if i % 2 == 0:
            dp.append(min(dp[i // 2], dp[i - 1] + 1))
            
        else:
            dp.append(dp[i - 1] + 1)

    return dp[n]