12852 - 1로 만들기(2)

횟수 찾는건 간단한데 할때마다 연산의 결과값 출력하는게 좀 헷갈림

 

1. 테이블 정의

d[i] = i를 1로 만들 때 필요한 연산횟수의 최솟값 

pre[i] = 최소 연산을 하기 위해서 i가 가야할 값

* 이 문제에선 정답이 여러개일 경우에 그중 아무거나 출력하면 됨

 

 2. 점화식

4를 예로 들어보면 4가 갈 수 있는 값은 3(-1) / 2(/2)가 있고, 이를 반대로 생각해보면 2에서 연산 한번 , 3에서 연산 한번 하면 4가 됨

그러면 2는 -1 or /2 로 1이 되고, 3은 /3으로 1이 될수도 있고 -1 / 2 로 두번 연산해서 1이 될 수도 있음

* 여기서 발견할 수 있는 게 d[i]는 d[i/2] d[i/3] d[i-1]의 값에 +1을 더한 것이고, 최솟값을 구해야 되기 때문에 저 셋 중 최솟값을 찾으면 됨

d[i] = Math.min(d[i/2], d[i/3], d[i-1]) + 1

pre의 경우에는 i를 연산해서 나온 결과값이 들어가면 됨

 

3. 초기값 정의하기

d[1] = 0 - 1이니깐

d[2] = 1 - 2에서 1 가는건 한번이니깐

pre[1] = 0 

pre[2] = 1 - 2에서 가야하는 최적의 연산값은 1이라는 뜻

 

이제 for문 돌려서 배열을 채워나가면 되는데

여기서 좀 헷갈리는게 저 3개의 값을 비교하는 게 좀 헷갈렸음 ... 사실 pre가 없었으면 그냥 값 세개 구해서 Math.min 해버리면 되는데

어떤 연산을 사용했는지를 알아야 되기 때문에 

일단 d[i] = d[i-1] + 1을 기본값을 설정함 // 당연히 -1은 어떤 숫자든 가능

2로 나눠지는데 그 값이 더 작으면 - d[i] 값을 바꾸고 pre[i]도 바꿈

마지막으로 3으로 나눠지고 작으면 또 바꿈

이렇게 하고 나면 d 배열에는 필요한 연산 최솟값이 담기고

pre에는 해당 값이 가야하는 최적의 수가 담겨 있음

 

pre[10] - 9 -> 이제 9가 가야하는 최적의 값을 찾아야됨 

pre[9] - 3

pre[3] - 1 

이런식으로 while문 돌리면 끝