[BOJ-1463] 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

[풀이]

0: 1로 입력 숫자 n과 인덱스의 혼동을 없애기 위해서 추가했다.

(즉, n=10일 때 1로 만드는데 최소연산 횟수를 DP[10]을 리턴 하기 위해서)

 

숫자 n이 1이 되기 위한 최소 연산 횟수를 구하려면…

1: 연산할 필요없이 1이므로, 1로 만드는데 필요한 연산횟수는 0이다.

2: DP[2]= MIN( DP[2-1]+1, DP[2//2]+1)

3: DP[3]= MIN( DP[3-1]+1, DP[3//3]+1)

4: DP[4]= MIN( DP[4-1]+1, DP[4//2]+1)

5: DP[5]= DP[5-1]+1

6: DP[6]= MIN( DP[6-1]+1, DP[6//3]+1, DP[6//2]+1)

 

---

[코드 (.py)]

# -*- coding: utf-8 -*-
import sys

def main():
    n=int(sys.stdin.readline())
    dp=[0]*(n+1)
    for i in range(2,n+1):
        #제일적게 1로 만드는 방법을 찾는다.
        dp[i]= dp[i-1]+1
        if i%3==0: #3으로 나눠떨어지는 수인가?
            dp[i]=min(dp[i], dp[i//3]+1) 
        elif i%2==0: #2로 나눠떨어지는 수인가?
            dp[i]=min(dp[i], dp[i//2]+1)
    print(dp[n])

if __name__=='__main__':
    main()

---

[코드 (.java)]