백준 1463번
1로 만들기
유명한 문제 중 하나로 알고 있다.
탐욕법에서도 유사한 문제가 있는데 탐욕법으로 해결할 때는
ex) 3으로 나누는 것이 2로 나누는 것보다 무조건 유리해야 한다.
그래야지 매 번 최선의 선택이
3으로 나누기 > 2로 나누기 > 1을 빼기 의 형식으로
우선 순위가 결정되기 때문이다.
이 문제는
3으로 나누는 것이 때로는 2로 나누는 것보다 비효율적일 수 있기 때문에 탐욕법으로 해결할 순 없다.
그렇다면 이 문제에서 Memoization을 어떻게 활용할 수 있을까?
핵심 중 하나는
3으로 나누는 행위, 2로 나누는 행위, 1을 빼는 행위 모두 다
연산의 횟수를 1회 증가시킨다는 공통점이다.
이를 통해 알 수 있는 가장 중요한 사실은
예를 들어, 4를 2로 나누면 2가 된다. 따라서 4를 1로 만드는 연산의 횟수는 2를 1로 만드는 연산의 횟수에 1을 더해주면 된다.
여기서 메모이제이션을 적용할 수 있다.
미리 작은 수의 결과를 구해서 저장해놓고 이를 큰 수에서 이용한다.
즉, n을 예를 들면
dp[n] = min(dp[n-1]+1, dp[n//2]+1, dp[n//3]+1) 로
표현할 수 있다.
추가적으로 적용되야 하는 조건은 정수이기 때문에
2 또는 3으로 나누어 떨어지는 파악해야 한다는 점이다.
소스 코드로 확인해보자.
편의를 위해서 1, 2, 3의 값은 미리 저장했다.
Whiplash We Flash