알고리즘 백준 1로 만들기 - 1463

(실버 3) 1로 만들기

이 문제는 시간 초과 제한이 있는 문제입니다.

계산할 필요가 없는 상황을 return 시켜서 시간을 단축해야 합니당

visit 배열을 만들어서 이미 방문한 곳을 return하는 방법도 있지만 

제가 생각해낸 방법은 현재 가장 작은 값보다 같거나 크다면 굳이 더 이상 작은 값을

찾아야하는 계산을 할 필요가 없다고 생각하여 그 상황이 온다면 return을 시켰습니다.

#include <iostream>
#include <algorithm>

using namespace std;


int maxs = 1000001;

void ja(int n, int c){
if(maxs < c) {
return;
}
if(n <= 3) {
if(c < maxs) {
maxs = c;
}
return;
}
c++;
if(n % 3 == 0) {
ja(n/3,c);
}
if(n % 2 == 0) {
ja(n/2,c);
}
ja(--n,c);

}

int main() {
int n;
cin >> n;

if(n == 1) {
cout << 0;
return 0;
}
ja(n,1);

cout << maxs;




return 0;

}