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

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

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

public class Solution {
	    public int solution(int n) {
	        int ans = 0;
	        
	        while(n!=1) {
	        	if(n%2==0) n/=2; //짝수면 절반으로 
	        	else {  //홀수면 -1 해주고 건전지++
	        		n-=1;
	        		ans++;
	        	}
	        }
	        return ans+1;
	    }
	}

소요시간 : 10분 

 

아이디어가 쉽게 떠오르지 않으면 어렵고, 쉽게 떠오르면 쉬운 문제입니다.

 

문제를 접했을 때 숫자 N: 1 이상 10억 이하의 자연수 이라는 제한사항을 보고

1부터 시작해서 완탐으로 찾는것은 불가능하다고 생각했고, N에서 뒤로 오는것을 생각했습니다.

 

우선 로직을 살펴보면

N이 짝수이면 N=N/2  해줍니다.

N이 홀수이면 N=N-1  해주고 건전지 소모는 하나 늘려줍니다.

 

이렇게 가다 N=1이 되면 while문을 빠져나오고 건전지 소모를 하나 늘려줍니다.