[201117] 점프와 순간 이동 - Summer/Winter Coding(~2018) (level2)

0. 문제유형 : Dynamic Programming(동적계획법)

1. 문제이해

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

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

(1) 주요 요구사항

① 2가지 액션을 통해 N만큼 떨어진 장소로 이동

- 점프 : 앞으로 K칸 이동. 건전지가 K만큼 사용.

- 순간이동 : (현재까지 온 거리) * 2 만큼 이동. 건전지 사용 없음.

② 2가지 액션을 취해 건전지 사용량을 최소화 = 최대한 점프의 횟수를 줄이기!!

 

(2) 제한사항

- N : 1이상 10억 이하의 자연수

- K : 1이상의 자연수

 

 

2. 전략

(1) Dynamic Programming(동적계획법)

2020/08/07 - [Coding Test/알고리즘] - Dynamic Programming (동적 계획법)

- 작은 문제에서의 최적의 결과여야 전체 문제에서 최적의 결과가 산출된다.

- 건전지 사용량 = (현재까지 온 거리)에서의 최적의 건전지 사용량 + 추가적으로 요구되는 건전지 사용량(점프)

- 재귀 함수를 통해 구현 가능

public int calcBattery(int n)
1. N이 짝수
N = (현재까지 온 거리) * 2
→ 추가적으로 요구되는 점프가 0회이므로 calcBattery(n) == calcBattery(n/2)
2. N이 홀수
N = (현재까지 온 거리) * 2 + 1
→ 추가적으로 요구되는 점프를 1회로 최소화
→ calcBattery(n) == calcBattery(n/2) + 1

 

 

3. 참고사항

(1) 재귀함수를 반복문 형태로도 변경할 수 있음

: 재귀는 n이 커져 깊이가 깊어지면 stack overflow가 발생할 가능성이 있음

▶ 무조건 안 좋은 것은 아니지만 주의할 필요성

while(n >= 1){
    if(n==1){
        ans++;  break;
    }else{
        if(n%2 != 0)    ans++;
        n/=2;
    }
}

cf> 꼬리 재귀 : 함수가 리턴된 후에 아무 작업도 하지 않도록 = return문에 추가적인 연산 없애기

    public int calcBattery(int n, int ans){
        if(n==1)    return  ans+1;
        else{
            if(n%2 == 0)    return calcBattery(n/2, ans);
            else    return calcBattery(n/2, ans+1);
        }
    }

 

 

4. 코드

import java.util.*;

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