[알고리즘]프로그래머스 12980번 - 점프와 순간 이동

프로그래머스 12980번 - 점프와 순간 이동

프로그래머스 12980번 - https://programmers.co.kr/learn/courses/30/lessons/12980

 

요구사항

1. 한 번에 K 칸을 앞으로 점프하거나, 현재까지 온 거리의 2배에 해당하는 위치로 순간이동하는 아이언 슈트를 착용하고 이동한다.

2. 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 들며, 순간이동을 할 경우는 건전지 사용량이 들지 않는다.

3. 거리 N을 이동하고자 할 때, 사용해야 하는 건전지 사용량의 최솟값을 반환하라.

 

요구사항 분석 및  풀이과정

1. 건전지 사용량의 최소로 하기 위하여 최대한 순간이동을 많이 하며, K 칸 점프를 최소한으로 하여야 합니다.

 

2. N번째 칸에 도착하는 방법은 K칸 점프해서 오거나, 순간이동으로 그전까지 온 거리의 2배에 해당하는 위치가 N인 경우 순간이동해오는 방법이 있습니다.

2-1. 후자의 경우는 그전까지 온 거리의 2배가 N 이여야 합니다. 즉 N이 짝수여야 한다는 의미입니다. 전자는 아무런 제한이 없습니다.

 

3. 2번의 시각처럼 이동을 관찰하는 관점을 시간의 역순으로 보면 편하며, 앞으로 거꾸로 관찰을 할 것입니다.

 

4. 만약 N이 짝수라면 N/2 번째 칸으로 순간이동이 가능하므로 순간이동을 하여 건전지 사용량을 줄이고, 그렇지 못한 경우(N이 홀수인 경우)는 어쩔 수 없이 최소한의 건전지 사용량을 위해 뒤로 1칸을 이동합니다.

4-1. 1칸만 이동하는 이유는, 1칸만 이동할 경우 해당 칸이 짝수 칸이 되므로 다음번에 (N-1)/2번째 칸으로 순간이동이 가능하기 때문입니다.

 

소스코드 작성

class Solution {

	public int solution(int n) {
		int result = 0;
		while (n != 0) {
			if ((n & 1) == 0) {
				n >>= 1;
			} else {
				n--;
				result++;
			}
		}

		return result;
	}
}

 

결과

 

소스코드 깃허브 주소

링크