[Python] BOJ(백준) 1463번 - 1로 만들기

링크

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

난이도(solved.ac 참고)

실버3

풀이

재귀형태의 다이나믹 프로그래밍으로 해결하였는데, 이렇게 푼 사람들이 많은 걸 보면 그냥 이렇게 풀라고 낸 문제 같다.

여기에서 dp배열의 값들은 1로 만드는 데 걸리는 횟수들이다.

여기에서 우선 dp[i] = dp[i-1] + 1은 그냥 1을 빼줬을 때에 해당한다. 그냥 빼기만 하면 이전 횟수에 비해 1회가 추가되는 것이 끝이기 때문.

2와 3으로 나눠질 경우, 횟수가 1회 추가되었으므로 dp[i//3]이나 dp[i//2]의 값에 +1을 해줬다. 그리고 그 값을 기존에 있던 dp[i-1]+1의 값과 비교를 해주었다.