2571. Minimum Operations to Reduce an Integer to 0

2571. Minimum Operations to Reduce an Integer to 0

https://leetcode.com/problems/minimum-operations-to-reduce-an-integer-to-0/

문제

풀이

n = 1부터 시작하여 n = n까지 가능 방향으로 생각을 해야 한다.
n = 1일 때 1 - 2^0이므로 = 1
n = 2일 때 2 - 2^1이므로 = 1이다.
n = 3일 때 3 - 2^1 또는 3 + 1 - 2^2방법이 있다.(문제에서 Add or subtract라고 주어줬다.) 즉 min(dp[1] + 1, dp[1] + 1) = 2이다.
n = 4일 때 4 - 2^2이므로 1이다.
n = 5일 때 5 - 2^2 또는 5 + 3 - 2^3, 즉 min(dp[1] + 1, dp[3] + 1) = 2가 된다.
이런식으로 n = n일 때 까지 Bottom-up방식으로 구현하였다.

n이 2^power라면 바로 subtract하면 되므로 dp[i] = 1을 해주고 power + 1을 해준다.
그렇지 않으면 Add,subtract부분을 확인해야 하는데 10 번째 줄과 같이 구현하였다.

결과