[백준] 1463번 (1로 만들기) <53>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 cache[n] 을 정수 n을 1로 만드는데 필요한 최소 연산의 횟수라고 가정해보자. cache[n]은 cache[n-1] 을 구한후 1을 더할수도 있고, cache[n]은 cache[n/2] 에다 곱하기 2를 하여 구할수도 있고, cache[n]은 cache[n/3] 에다 곱하기 3을 하여 구할수도 있다. 즉, cache[n]은 cache[n-1], cache[n/2], cache[n/3] 각각의 case 에서 연산을 한번만 더하면 도달할수 있습니다. 우리의 목표는 최소의 cache[n]을 구하는 것 이니 cache[n] = min(cache[n-1], cache[n/2], cache[n/3])+1 이라는 점화식이 완성됩니다. 내 코드...

원문링크 : [백준] 1463번 (1로 만들기) <53>