문제링크

문제 이해

[ 입력형태 / 조건 ]

n
아이언 슈트 구매자가 이동하려는 거리 | 8 | 1 이상 10억 이하의 자연수

[ 문제 ]

사용해야 하는 건전지 사용량의 최솟값을 return
점프 or 순간이동의 방법으로 이동 가능
점프 : 한번에 원하는 칸을 이동할 수 있지만, 이동한 칸만큼 건전지가 사용됨
순간이동 : 이때까지 이동해온 칸의 2배로 이동가능하고 건전지를 소모하지 않음

[ 풀이 ]

가능하면 순간이동으로 목적지에 도달하는것이 이득임(그리디)
순간이동은 전에 이동한 거리의 2배이므로, 전에 이동한 거리가 짝수가 아니면 한칸은 점프를 해서 이동했어야 함

예시 - n이 5000인 경우)

순서	현재 위치	이동 방법	이동 결과	소모 건전지
1	5000	순간이동	2500	0
2	2500	순간이동	1250	0
3	1250	순간이동	625	0
4	625	한칸점프	312	1
5	312	순간이동	156	0
6	156	순간이동	78	0
7	78	순간이동	39	0
8	39	한칸점프	19	1
9	19	한칸점프	9	1
10	9	한칸점프	4	1
11	4	순간이동	2	0
12	2	순간이동	1	0
13	1	한칸점프	0	1

=> 전체 소모 최소 건전지량 : 5

---

코드

> [성공] 1차 시도 : 구현

• 생각한 풀이 그대로 구현

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;
        while(n!=0){
            if(n%2 == 1){
                ans+=1;
            }
            n/=2;
        }
        return ans;
    }
}

Tip : 입력 변수의 크기가 크다면, 규칙을 찾아 연산 횟수를 줄여야 한다.