백준 1463 1로 만들기 파이썬 다이다믹 프로그래밍(DP)

처음에는 이 식이 이해 되지 않았다. dp[i] = dp[i-1] + 1 이 식의 뜻은 예를들어 i = 10 인경우 9를 1로 만드는 최소 경우의 수에서 +1을 해줘라, 10 - 1을 해주고 1을 만드는 최소의 경우의 수를 구하는 공식이다. + 1을 해주는 이유는 10에서 -1을 해주는 연산을 한 번 했으니 +1을 해주는 것이었다. dp[i//2] + 1, dp[i//3] + 1 이것도 나누면서 연산을 한 번 수행했으므로 + 1을 해주는 것이었다. 10을 1로 만든다고 가정했을 때 나오는 연산 10 -> 5 -> 4 -> 2 -> 1 (/2, -1, /2, -1) 연산 4개 10 -> 9 -> 3 -> 1 (-1, /3, /3) 연산 3개 이런식으로 나오는데 둘 중에서 연산의 수가 제일 작은 것은 3개 이므로 10을 입력하면 3이 나온다. 최종 코드 n = int(input()) dp = [0] * (10**6 +1) dp[2] = 1 dp[3] = 1 for i in range(4...

원문링크 : 백준 1463 1로 만들기 파이썬 다이다믹 프로그래밍(DP)