1387. Sort Integers by The Power Value

1387. Sort Integers by The Power Value

https://leetcode.com/problems/sort-integers-by-the-power-value/

문제

풀이

이 문제를 DP로 적용하는 것은 단순하다. 예를 들어
13 => 9(13 --> 40 --> 20 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)이고
14 => 17(14 --> 7 --> 22 --> 11 --> 34 --> 17 --> 52 --> 26 -> 13 -> ...)이다.
13 => 9라는 것을 구하고 나서 14구하는 과정에서 13이 나온다면 13은 9라는 것을 이미 알고 있으므로 9를 리턴하면 되는 것이다. 따라서 1+1+1+1+1+1+1+1+9 = 17이다.
시간적인 측면에서 최적화를 한 것과 하지 않는 것은 크게 차이난다.

결과