C++:: 프로그래머스 < 점프와 순간 이동 >

문제자체가 전형적인 bfs형식의 문제여서 입력조건의 범위가 10억이라는 점을 망각하고 그냥 풀어버려서 시간초과가 난 문제이다. 생각해보면 간단한 문제인데 사고가 굳어서 제대로 생각해내지 못한 문제이다. 아래코드가 간단하고 명확한 코드이다.

// 시간초과 코드
#include <queue>
using namespace std;

int solution(int n) {
    int answer = __INT_MAX__;
    queue<pair<int,int>> q;
    q.push({1,1});
    while (!q.empty()) {
        pair<int,int> cur = q.front();
        q.pop();
        if (cur.second >= answer || cur.first >= n) {
            if (cur.first == n) answer = min(answer, cur.second);
            else if (cur.first > n) answer = min(answer, cur.second + n - cur.first/2);
            continue ;
        }
        q.push({cur.first+1, cur.second+1});
        q.push({cur.first*2, cur.second});
    }
    return answer;
}

정답 코드

#include <iostream>
using namespace std;
 
int solution(int n) {
    int ans = 0;
    while(n > 0) {
        if(n % 2 == 0) n /= 2;
        else {
            n -= 1;
            ans++;
        }
    }
    return ans;
}