반응형 D1 [이코다] 다이나믹 프로그래밍 p.217 - 1로만들기 처음 풀이(오답) def solution(num): cnt=0 def calculate(x): if x%5==0: return x//5 elif x%3==0: return x//3 elif x%2==0: return x//2 elif x>1: return x-1 while num!=1: num = calculate(num) cnt+=1 solution(26) #5 그리디처럼 푼 처음 풀이 첫 단계에 위와같은 순서로 해야지 가장 작은 연산의 횟수가 나온다고 생각했다. 하지만 위와 같이 하면 2로 먼저 나누게 되고 그러면 답안과 다르게 5라는 답이 나온다. 이 무제는 다이나믹 프로그래밍이고 그 근거는 1) 부분적인 연산의 합이 답이 된다. 2) 작은 문제로 나눠진다. 다이나믹 프로그.. 2021. 8. 23. 이전 1 다음 반응형
