[문제 조건]
움직이는 방법은 2가지가 있다
- 앞으로 K만큼 이동 -> K만큼 건전지를 사용함
- 위치 a에서 2*a의 위치로 순간이동 -> 건전지 사용량 없음
따라서, 최대한 순간이동을 하되 순간이동으로 움직일 수 없는 거리만 K만큼의 건전지를 사용해 이동한다.
T[i] : 위치 i로 이동할 때, 최소 건전지 사용량
(1) n=1일 경우(base-case)
: 앞으로 1만큼 이동한다 (T[1] = 1)
(2) n=2일 경우
: 위치 1에서 순간이동을 사용한다 (T[2] = T[2/2] = 1)
(3) n=3일 경우
: 위치 1에서 순간이동을 해서 위치 2로 이동한다. 그리고 앞으로 1만큼 이동한다. (T[3] = T[3/2] + 1 = 2)
(4) n=4일 경우
: 위치 2에서 순간이동해서 위치 4로 이동한다. (T[4] = T[4/2] = 1)
문제 접근 방식
- 이동하려는 위치 n이 짝수인 경우 위치 n/2에서 순간이동을 하면 된다
- 이동하려는 위치 n이 홀수인 경우 위치 n/2에서 순간이동을 해 위치n-1로 이동하고 앞으로 1만큼 이동한다.
즉, T[i] = T[i/2] + (i%2) 이다.
public int solution(int n) {
int ans = 0;
//arr[i] : 위치 i로 이동할 때, 최소 건전지 사용량을 저장한다
int[]arr = new int[n+1];
//base-case
arr[0] = 0;
arr[1] = 1;
//induction step
for(int i=2; i<=n; i++) {
arr[i] = arr[(i/2)] + (i % 2);
}
ans = arr[n];
return ans;
}
문제 조건에 따르면 입력의 크기는 10억 이하의 자연수이다.
DP방식으로 알고리즘을 작성할 경우, 시간복잡도는 O(n) 이기 때문에 1초를 초과하게 되어 시간초과(Fail)가 발생할 것이다.
이동하려는 위치가 n일 경우, 위치 n/2에 대한 최소 건전지 사용량을 알아내면 된다.
EX) N=4일경우
T[4] : T[2]를 구하는 함수를 호출해서 리턴
T[2] : T[1]를 구하는 함수를 호출해서 리턴
T[1] : 거리 1이 base-case이므로 1을 리턴
따라서, 시간복잡도는 O(logN)이 된다.
public int divCon(int n) {
//종료부
if(n == 1) { return 1; }
//재귀함수 호출부(순환부)
else { return (divCon(n/2) + (n%2)); }
}
public int solution(int n) {
int ans = 0;
//분할정복해, 문제의 답을 알아낸다
ans = divCon(n);
return ans;
}