Algorithm/DP1 백준 1463번 : 1로 만들기 단순 그리디 방식으로 푸는 것이 아니라 10->9->3->1 처럼 1을 빼고나서 3을 나눴을 때 더 빠르게 1로 만들 수 있기 때문에 동적계획법으로 접근하면서 메모이제이션 기법을 사용해야 한다. n = int(input()) dp = [0 for _ in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1]+1 if i%3 == 0: dp[i] = min(dp[i], dp[i//3]+1) if i%2 == 0: dp[i] = min(dp[i], dp[i//2]+1) print(dp[n]) 1. 왜 dp 리스트를 n+1까지 0으로 만드는가? 예를 들어서 n이 10이라고 했을 때 dp[10]까지 최소값을 저장하면서 연산할 것이기 때문에 리스트에 +1을 더해야 한다. 2.. 2021. 7. 13. 이전 1 다음
