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

문제

• 문제는 이 곳에 가시면 있습니다.

힌트

• 일부의 최적의 해를 사용해 전체의 최적의 해를 구한다.

소스 코드 (1차 시도)

//[프로그래머스]
//점프와 순간 이동

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> gMin;

int getMin(int n) {
  if (gMin[n] != 0) return gMin[n];
  if (n % 2 == 0) {
    if (getMin(n/2) < (getMin(n-1) + 1)) {
      gMin[n] = getMin(n/2);
    } else {
      gMin[n] = getMin(n-1) + 1;
    }
  } else {
    gMin[n] = getMin(n-1) + 1;
  }
  return gMin[n];
}

int solution(int n) {
    int answer = 0;
    gMin.reserve(n+1);
    for (int i = 1; i <= n; i++) {
      gMin[i] = 0;
    }
    gMin[1] = 1;
    gMin[2] = 1;
    answer = getMin(n);
    gMin.clear();
    return answer;
}

- 실패 (정확성 통과, 효율성 0점)

 

실패한 원인

• 메모리 사용량이 많았다
• 계산을 너무 많이 했다

해결 방법

• 일일히 min 값을 구해 저장하지 않고 어떤 계산식을 이용하면 되지 않을까?

소스 코드 (2차 시도)

//[프로그래머스]
//점프와 순간 이동

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    int answer{0};
    while (n != 0) {
      if (n % 2) {
        answer++;
        n -= 1;
      }
      else n /= 2;
    }
    return answer;
}

- 성공 (정확성, 효율성 통과)