백준 1463 : 1로 만들기

백준 1463 1로만들기

https://www.acmicpc.net/problem/1463

해설

dp로 불어보았다. 

문제를 딱 봤을 때 우선 음.. 확실히 3으로 나누는 것이 이동수를 크게 줄이는 이득부분이니까 나누는게 좋다. 라고 생각했고, n에서 1까지 내려가는 것을 연산하였다.

그런데 반례는 예제에서도 있듯이 10은, 10 ->9->3->1 이 최소이동이며  내가 생각한대로 하면

10->5->4->2->1 이므로 이동횟수가 하나 더 많았다.

dp의 배열을 이용하면서 1에서부터 차근차근 해당수로 올라가면서 1에서부터의 최소거리를 구한다면 우리가 원하는 방식으로 알고리즘은 동작한다. 어떤 수 n는 default로 하나 작은 수[n-1] 에서 1을 더한만큼의 거리를 가진다. 그리고 그게 2로 나누어지고 d[n-1]+1보다 d[n/2]+1이 작다면 대체, 그게 3으로 도 나누어지고 d[n-1]+1, d[n/2]+1 보다 작다면 d[n/3]+1 로 대체한다. 

6인경우를 생각해보자. 6은 확실히 d[5]+1, d[3]+1, d[2]+1 이다. 이 셋중에서 무엇이 제일 작은 값인지는 d 배열의 값을 알아야 가능하다. 그래서 코딩에서는 비교하는 조건문이 들어가는 이유다. 반드시 배수가 +1보다 효율적인 반례는 위에서 살펴보았던 자연수 10이다.

10은 확실히 d[9]+1, d[5]+1 이다. 이 둘중에서 작은 값은 d[9]+1 이기 때문이다.

n의 경우는 어떨까? 잘 작동한다. 이는 모든 자연수 입력값에서도 잘 동작한다. 

왜그럴까? 우리는 차근차근 모든 경우의 수 (+1, *2, *3) 를 비교하며 숫자들의 최소 거리를 저장하며 진행했기때문에 앞으로 진행 될 수도 항상 최소 거리이다. 이 문제가 나한테 dp 입문이였다.

소스보기

 https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/p1463.c