1463번 1로 만들기

문제링크 : www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

---

<알고리즘>

결과값을 계산해 놓는 배열이용 & 최소의 경우 +1로 횟수 늘려가기

  1) 결과값을 계산할 배열을 선언 & 초기화

  2) index가 0, 1 일 경우는 0으로 고정 시켜놓기

  3) index가 2이 이상일 경우부터, 1씩 뺏을 경우(즉, d[index-1]의 값 +1)로 일단 변경

     3-1) 혹시 i가 3으로 나누어지며, d[index//3]+1의 값이 앞서 변경해놓은 값보다 작을 경우 변경

     3-2) 혹시 i가 2으로 나누어지며, d[index//2]+1의 값이 앞서 변경해놓은 값보다 작을 경우 변경

  4) index가 N이 될때까지 쭉 수행 후, d[N]값 출력

  

 

 

ex) N이 6일 경우,

    d[0]~d[5]까지는 앞서 결과값이 나와있는 상태 있음

    (d[0]=0    d[1]=0    d[2]=1     d[3]=1     d[4]=2     d[5] = 3)

    i = 6인 상황,

    3) d[6] = d[5]+1 = (d[4]+1)+1 = ((d[3]+1)+1)+1 = (((d[2]+1)+1)+1)+1 =4

    3-1) i%3==0 , d[6] = (d[2])+1 = 2

    3-2) i%2==0 , d[6] = (d[3])+1 = (d[1]+1)+1 = 2

    => d[6] = 2

  위에선 쉬운 이해를 위해 계산 순서를 풀어써서 반복이 많아보이지만

실제론 앞에서 부터 계산 했기 때문에 시간복잡도는 O(N)이다

 

 

메모리 : 37024KB   시간 : 528ms

import sys
N = int(sys.stdin.readline())
d = [0 for _ in range(N+1)]
for i in range(2,N+1):
    d[i]=d[i-1]+1
    if(i%3==0 and d[i//3]+1<d[i]):
        d[i] = d[i//3]+1
    elif(i%2==0 and d[i//2]+1<d[i]):
        d[i] = d[i//2]+1
print(d[N])

 

 

+) 참고 : 메모이제이션 알고리즘    hongku.tistory.com/161

알고리즘 :: 다이나믹 프로그래밍(DP) - 피보나치(Fibonacci) C/C++ 구현, 메모이제이션