anscjfeodud   4년 전

왜 틀리는지 모르겠습니다.

iljimae   4년 전

반례를 드리자면 n = 17일때 5번만의 연산을 통해서 1을 만들 수 있지만, 위 코드는 6을 출력합니다. 

그리고 이 문제는 아마 위 코드처럼 탐욕적으로 해결할 수 없을거에요. 다이나믹 프로그래밍 문제인만큼 모든 경우를 다 시도해보는 코드를 작성하셔야 할거에요. 

예를 들어서 dp[i] = i를 1로 만들기 위한 연산의 횟수라고한다면, i가 2랑 3으로 나누어질때 dp[i] = min(dp[i/2],dp[i/3],dp[i-1])+1 과 같은 점화식을 사용하실 수 있습니다.  

댓글을 작성하려면 로그인해야 합니다.