bottom-up

[백준] 1463. 1로 만들기 - 파이썬

https://www.acmicpc.net/problem/1463 풀이 1 정말 단순하게 생각하면, "당연히 3으로 나누는게 가장 빨리 숫자를 줄일 수 있고, 그 다음이 2로 나누는 거고, 그 다음에 1을 빼는 것을 택하는 게 제일 유리한 거 아닌가?" 라고 생각할 수 있다. (약간의 Greedy 느낌!) 그러나, 10의 Input 예시만 생각해 봐도, 위와 같은 알고리즘으로는 10은 2로 나눠지므로, 10/2 = 5 5는 3, 2로 나눠지지 않으므로, 5-1=4 4는 2로 나눠지므로, 4/2 = 2 2는 2로 나눠지므로, 2/2 = 1 로 4번의 연산만에 1이 된다. 그러나, 첫 번째 단계에서 1을 빼는 것을 택한다면, 10 - 1 = 9 9 / 3 = 3 3 / 3 = 1 로 3번의 연산만에 1을 만..