Lv.2 점프와 순간 이동 [C++]

문제 링크

성공 여부(걸린 시간): 성공(12분 21초)

아이디어

우선 해당 문제의 코드를 보기전에 무조건 풀고 오시길 강.력.추.천 드립니다. 

 

스포방지

 

우선 문제에서 제시한 이동 방법은 아래와 같이 2가지이다.

1. K칸 점프 (건전지 사용량 K)
2. 이동한 만큼 순간이동 (건전지 사용량 0)

그래서 처음에 떠올린 방법은 BFS를 통해서 각 상태마다 2번 이동이 가능하다면
1번과 2번 방법 모두 시도해서 다음 큐로 넣어주고 그게 아니라면 1번만 시도해서 다음번 위치, 건전지 사용량을 넣어준다.

그렇게 목적지인 N까지 도달하는데 드는 최소한의 비용을 구하고자 했다.

그런데 충격적이게도 N이 10억이하의 자연수이므로 모든 경우의 수에 대해서 진행을 하면 시간초과가 발생하지 않으면 내 상식이 부정되는 조건을 발견하게 되어서 다른 방법을 생각하게 되었다.

그래서 생각한 여러 방법은

 

1. DP를 통해서 10억개의 배열 또는 map을 활용해 목적지 N까지 도달하는 최소 배터리 사용량을 구하는 방법

-> 배열이 아닌 map을 사용하더라도 메모리나 시간에서 초과가 날듯하다.

 

2. N부터 역으로 짝수일 경우 최선의 이동 방법인 순간이동으로 N/2를 하고 홀수일 경우 1을 줄여 결국엔 0에 도달하는 방법

-> 가능.!

5일 경우부터 예제 케이스를 내 생각대로 해보았다.

 

N = 5
5 -- 
4/2
2/2
1 --

정답 : 2

 

N = 6
6/2
3--
2/2
1--

정답 : 2

N = 5000
5000/2
2500/2
1250/2
625--
624/2
312/2
156/2
78/2
39--
38/2
19--
18/2
9--
8/2
4/2
2/2
1--

정답 : 5

나의 마지막 접근이 타당해 보인다. 

사실 이렇게 접근을 했다면 코드는 정말 Level 0 수준으로 간단하다.

오히려 어렵게 생각할수록 어려워지는 문제였다.

 

풀이 코드

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;
    while(n>0){
        if(n % 2==0){
            n/=2;
        }
        else{
            n--;
            ans++;
        }
    }

    return ans;
}