입력받은 수를 3으로 나누기, 2로 나누기, 1 빼기 이 세 가지 연산을 이용하여 1로 만드는 최소의 연산 횟수를 구하는 문제이다. 얼핏 보면, 3으로 나누는 연산이 가장 수를 많이 줄여주니까 3으로 나누고, 3으로 나누지 못하면 2로 나누고, 그러지 못하면 1을 빼는 식으로 구할 수 있는 간단한 문제인 것 같이 보인다. 하지만 이것은 탐욕 법으로 계산하는 방법이며, 항상 최적해를 구할 수 없다. 예를 들어, 10을 1로 만드는 방법을 탐욕법으로 구한다면 10 -> 5 -> 4 -> 3 -> 1으로 총 4회의 연산이 필요하다. 하지만, 동적 계획법으로 연산을 하면 10 -> 9 -> 3 -> 1 로 총 3회의 연산만으로 1로 만들 수 있다. 따라서, 모든 경우의 수를 살펴 보아야 한다. import ja..
