프로그래머스 LV2 - 점프와 순간 이동.

 

어렵고 복잡해보이나 조건을 하나씩 풀어가면 어렵지 않다.

구체적인 예를 들어가며 답을 찾아갔다.

최대한 많은 수를 순간이동으로 접근해야하는데, 그 수가 홀수라면 결국엔 마지막에 +1을 위해 점프를 할 수 밖에 없다.

이 원리를 적용해보면 홀수일때 -1을 해 짝수를 만들어주고,

그수를 다시 2로 나눠봤을때 짝수가 된다면 순간이동으로 접근할 수 있으니 그대로 통과,

홀수가 된다면 결국에 점프 1이 필요하다.

이프로세스를 반복해 2로 나눈 나머지가 1이 될때마다 카운트를 1 해주는 과정을 주어진수 n이 1이될때까지 반복해준다.

이때 반복문은 특정횟수가 아닌 조건에 의한 반복이기 때문에 while문을 사용해준다.

while문이 1이되는 순간은 카운트가 세지지 않으나, 0부터 시작하기 때문에 1을 만들기 위해 점프해야하기 때문에, cnt +1이 답이다.

 

 

def solution(n):
    ans = 0
    cnt = 0
    
    # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    # 점프를 최소한만 하자. 
    # 6과 7은 본질적으로 같다.결과에 +1을 한게 최적의 값이기 때문.
    # 짝수에 대해 어떤 수든 소인수 분해를 해보자. 그리고 최대한 2로 나누고, 나오는 홀수에 대해서는 이 +1을 적용해줘야한다.
    
    # 즉 34를 예로 들어보자.
    # 2 x 17 == 2x(16+1)
    # 38를 예로 들어보자
    # 2x 19 == 2 x (18 +1)
    # 9
    # 100을 예로 들어보자
    # 2 x 50 == 2 x 2 x 25 
    # 24 == 8 x 3
    # 우선 홀수라면 카운트를 1 늘려준다.
    # 짝수를 많들어 2로 나눠준뒤 그 결과에 대해 홀수라면 또 카운트 1 을 늘려준다.
    # 1이 될때까지 계속 나누다보면 그 총카운트 값이 답이 된다.
    
    while n != 1:
        if n%2 == 1:
            n -= 1
            cnt += 1
        else:
            n /= 2
            
    ans = cnt + 1

    return ans