[프로그래머스] 점프와 순간 이동 (C++) - Lv.2

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

개요

문제를 읽자마자 dp로 풀어야겠다는 생각이 바로 들었다.

뭔가 이전에 풀어본 계단 오르기 유형의 문제와 비슷하게 접근하면 될 것 같다는 생각으로 접근했다.

 

틀린 코드 (첫 제출)

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

int solution(int n)
{
    vector<int> dp(n + 1); // i번째 칸까지 가는데 사용한 최소 건전지 사용량
    dp[1] = 1; dp[2] = 1;
    for (int i = 3; i <= n; i++){
        if (i % 2 == 0)
            dp[i] = min(dp[i - 1] + 1, dp[i / 2]);
        else
            dp[i] = dp[i - 1] + 1;
    }
    return dp[n];
}

테스트 케이스 3개를 모두 통과해서 당연히 맞았겠거니 하고 바로 제출했다.

그런데 채점 결과는 다음과 같았다.

 

정확성 테스트는 모두 통과했는데, 효율성 테스트는 모두 실패하는 결과를 얻었다...!

 

O(N)으로 구현했는데도 시간 초과가 나길래 문제 조건을 다시 한 번 보았는데,

N의 범위가 1 <= N <= 10억 이었다....

O(N)으로 해도 당연히 시간 초과가 날 만했다...ㅋㅋㅋㅋㅋ

 

그래서 N 값을 그대로 사용하지 않고, 최대한 어떤 방식으로든 줄어든 N 값을 사용해야겠다고 생각했다.

 

주목했던 점은 순간 이동은 (현재까지 온 거리) X 2 로 이동한다는 것이였다.

 

순간 이동 시에는 건전지 사용량의 변화가 없기 때문에

당연하게도, 순간 이동 횟수가 최대한 많을수록 최소 건전지 사용량을 구할 수 있겠다고 생각했다.

 

 그래서 N을 계속 2로 나누면 되겠다는 방식으로 접근했다.

2로 나눈다는 것은 그 이전 위치에서 순간이동을 했다는 의미이기 때문에 건전지 사용량의 변화가 없는 것이다.

 

그러나, 여기서 주의할 점이 있다.

N이 짝수인 경우에는 당연히 2로 나눌 수 있다.

예를 들어, N = 200인 경우에는 2로 나누면 N = 100이 되는데, 이는 100이라는 위치에서 순간이동을 해서 200이라는 위치로 이동한 것이다.

 

그러나, N이 홀수인 경우에는 바로 2로 나눌 수 없다.

즉, 현재 위치가 홀수인 경우에는 이전 위치 어디에서든 순간 이동으로는 현재 위치에 올 수 없음을 의미한다.

N이 홀수인 경우에는 짝수인 N - 1에서 1만큼 점프를 하는 방법이 최선이다.

이 때, 1만큼 점프함으로써 건전지 사용량은 1만큼 증가한다.

그리고, N - 1에 대해서 다시 2로 나누는 것이다.

 

위의 방식대로,

N이 짝수일 때는 2로 나누고, N이 홀수일 때는 1을 뺀 다음 건전지 사용량을 1 증가해주는 방식으로

N이 0이 될 때까지 진행하면 된다. (N = 0은 즉 처음 위치를 의미한다.)

 

구현한 코드는 다음과 같다.

 

정답 코드

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

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

 

깨달은 점

일단, 문제 조건을 처음에 제대로 읽어야겠다고 느꼈다.

문제 조건만 제대로 읽었어도 금방 풀 수 있는 문제였다고 생각한다.

다음부터는 테스트 케이스는 다 맞더라도 제출 전에 다시 한 번 문제 조건을 읽어보는 습관을 들여야겠다.