동적계획법
-
[문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급 p.83)알고리즘 2017. 1. 21. 18:46
이 책의 동적 계획법 (Dynamic Programming)의 첫번째 문제로 이 문제가 등장한다. 앞에서도 등장했던 문제로, 풀이를 보면 이 문제를 왜 이렇게 풀어야 하는지 조금 의심스럽긴 하다. 계산량이 줄어든다고 보기도 어렵고, 주어진 n까지 (최대 50,000) 메모리를 확보해야 한다. 앞선 포스트 ([문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급, p18))에서도 풀이를 한 적이 있지만, 다시 한번 풀이를 작성해 보았다. 또한 pow()와 log10()는 직접 구현하여 라이브러리 참조를 최소화하였다. 나머지 부분은 풀이를 참고하기 바란다. import java.util.Scanner; public class ReverseNumSol84 { // 최대 숫자까지 다이나믹 테이블 선언 publi..