Programmers: 점프와 순간이동

문제

• https://programmers.co.kr/learn/courses/30/lessons/12980
• 분류: 구현 / 수학[??] / DP[Bottom-Up]

핵심

• K칸을 앞으로 점프할 때, K만큼 건전지 사용
• 순간이동 = 건전지 사용 X
  • 그러나, 순간이동은 (현재까지 온 거리) * 2의 위치로 이동
  • 즉, 현재 위치가
    • 1이면 순간이동 후 위치는 '2'
    • 5이면 순간이동 후 위치는 '10'
• 예제를 따라 해보면 다음과 같은 규칙 존재
  • '1'의 위치로 가는 가장 효율적인 방법은 1로 점프 -> 배터리 1 소모
  • '2'의 위치로 가는 가장 효율적인 방법은 1로 점프 + 2로 순간이동 -> 배터리 1 소모
  • '3'의 위치로 가는 가장 효율적인 방법은 '2'의 방법 적용 후 1로 점프 -> 배터리 2 소모
  • '4'의 위치로 가는 가장 효율적인 방법은 '2'의 방법 적용 후, 4로 순간이동 -> 배터리 1 소모
  • '5'의 위치로 가는 가장 효율적인 방법은 '4'의 방법 적용 후, 1로 점프 -> 배터리 2 소모
• 즉, 홀수인 경우
  • 'n'의 위치로 가는 가장 효율적인 방법은 '(n-1) / 2'의 방법 적용 후, 1 점프
    • (n-1) / 2 배터리 + 1 성립
• 즉, 짝수인 경우
  • 'n'의 위치로 가는 가장 효율적인 방법은 'n / 2' 방법 적용[끝]
    • n/2 배터리 성립
• 표 작성 예[input = 5000]

Reach	Battery
5000	5
2500	5
1250	5
625	5
624	4
312	4
156	4
78	4
39	4
38	3
19	3
18	2
9	2
8	1
4	1
2	1
1	1

알고리즘

• Binary Vector 생성
  • [최대한 짝수로 이루어진 벡터, input 수 분해]
  • Input이 5라면, 1부터 5까지 2로 증가하는 형식의 벡터 만들기
  • input = 5
    • output_vector = 5, 4, 2, 1
  • input = 5000
    • output_vector = 5000, 2500, 1250, 625, 624, 312, 156, 78, 39, 38, 19, 18, 9, 8, 4, 2, 1
• 하나씩 보면서 진행
  • output_vector의 맨 끝[=1]부터 보기 시작함
    • 수가 1인 경우에는 배터리 1로 설정[왜나, 1인경우에는 1이 가장 효율적]
  • 그게 아닌 경우[현재 수와 바로 전의 수 비교]
    • 현재 수와 바로 전의 수가 1차이인 경우 -> 배터리 1 증가
    • 현재 수와 바로 전의 수가 2배 차이인 경우 -> 아무것도 안함[배터리 유지]

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> make_vector(int destination) {
    vector<int> tmp_vector;
    tmp_vector.push_back(destination);
    while (destination != 1) {
        if (destination % 2 == 0) {
            tmp_vector.push_back(destination / 2);
            destination /= 2;
        } else {
            tmp_vector.push_back(destination - 1);
            destination--;
        }
    }

    return tmp_vector;
}

int solution(int destination) {
    // let destination = 5
    vector<int> binary_vector = make_vector(destination);
    int battery = 0;

    for (int i = binary_vector.size() - 1; i >= 0; i--) {
        if (binary_vector[i] == 1) {
            battery = 1;
        } else {
            if (binary_vector[i+1] * 2 == binary_vector[i]) {
                continue;
            } else {
                // cout << binary_vector[i+1] << ", " << binary_vector[i] << endl;
                battery++;
            }
        }
    }

    return battery;
}