성능 요약
- 메모리: 52.1 MB, 시간: 0.02 ms
구분
- 코딩테스트 연습 > Summer／Winter Coding（～2018）
Answer Code1(2023.02.06)
import java.util.*;
public class Solution {
public int solution(int n) {
int ans = 0;
while(n != 0) {
if(n % 2 == 0) {
n /= 2;
} else {
n -= 1;
ans++;
}
}
return ans;
}
}
문제 풀이
-
이동하는 방법1,2 : [1] 한 번에 K칸을 앞으로 점프하는 방법 / [2] (현재까지 온 거리) X 2에 해당하는 위치로 순간이동하는 방법
점프는 건전지 사용량이 들고,순간이동은 건전지 사용량이 줄지 않는다.
-
건전지 사용량의 최솟값을 만들기 위해서는 최대한 아이언 슈트를 착용하고
순간이동을 하는 방법을 활용하고, 필요할 때에만점프방법을 사용한다.
-
[결론]
-
N이 0이 될 때까지
-
N이 짝수라면 반을 나누고 N / 2 (순간이동)
-
N이 홀수라면 -1을 빼며 점프하여 최솟값을 구한다.
-
Review
-
N이 6일 때 6까지 최대한
순간이동방법을 써서 건전지의 사용량의 최솟값을 구하면 되는 문제였다. -
아이디어는 6부터 시작해서 0까지 가는 Top-Down 방식으로 사용하면 간단하게 풀 수 있는 문제였는데,
아이디어가 바로 떠오르지 않아서 고민한 시간이 꽤 길었다. (20~30분)
-
머리로 떠오르지 않으면 그림을 그려보자!