최소 단계는 이러한 작업 중 하나를 수행 할 수 있습니다,

Question

는 숫자 X를 감안할 때 1 (변형)에 N을 줄이기 위해 :

1 씩 감소 X 1.

2 증가 X에 의해 1.

3의 경우 X는 3의 배수가 당신에 의해 X를 나눌 수 있습니다 3.

나는이 문제에 대한 O (n)의 DP 솔루션이 있다고 생각하지만, 어떻게 1 < = X <을 위해 그것을 해결하기 = 10^9? (N은 ~ 3^N, 그것이 ~ 걸리면 2N 간다)

Answer 1

이것은 O 작동 (2log_3N) 시간의 일거수 일투족이 같이

• N 개조 3 == 0 : 3
분할기
• N 모드 3 == 1 : 빼기 1
• N 모드 3 == 2 : 1

그래서 우리는 우리가해야 할 3의 요인에 의해 줄이기 위해 최대 2 이동이 필요합니다 추가 ~ N 타임스.

<input type='number' id='nm'/> 
 
<button onclick='go();'>Go</button> 
 
<br> 
 
<span id='out'/> 
 
<script> 
 

 
function go() { 
 
var n=nm.value; 
 
var nc=0; 
 
out.textContent=n; 
 
while (n>1) { 
 
    n3=n%3; 
 
    switch (n3) { 
 
     case 0: {n/=3;break;} 
 
     case 1: {n--;break;} 
 
     case 2: {n++;break;} 
 
    } 
 
    nc++; 
 
    out.textContent+=','+ n; 
 
    } 
 
out.textContent+=' ::'+ nc; 
 
} 
 

 
</script>