프로그래머스. 점프와 순간 이동

https://programmers.co.kr/learn/courses/30/lessons/12980#

코딩테스트 연습 - 점프와 순간 이동

 

처음 생각한건 bottom-up 방식으로 1부터 n까지 답을 쌓아올리는 방법이다.

현재 칸을 i라고 하면 바로 이전 칸인 i-1가 되는데 필요한 건전지량,

i/2가 2로 나뉘어 떨어진다면 i/2칸의 건전지량,

나뉘어 떨어지지 않는다면 i/2-1칸의 건전지량+1 중 작은 값이 현재 칸 i에 필요한 최소 건전지량이다.

 

예를들어 n=6이라면 

1칸 = 1

2칸 = 1

3칸은 1칸에서 순간이동 하면되므로 1 or 전칸인 2칸에서 +1칸 해서 2, 둘 중 작은 값인 1

4칸은 2칸에서 순간이동 하면되므로 1 or 전칸인 3칸에서 +1칸 해서 2, 둘 중 작은 값인 1 

5칸은 2칸에서 순간이동 한 후에 +1칸 이므로 2, 전칸인 4칸에서 +1 해서 2, 둘 중 작은 값인 2

6칸은 3칸에서 순간이동 하면되므로 1, 전칸인 5칸에서 +1칸 해서 3, 둘 중 작은 값인 1 

 

이런 식으로 생각했는데 n이 10억 까지이기 때문에 메모리 문제가 발생한다.

어떻게 배열을 작은크기로 만들고 값을 교체하는 방법이 없을까 생각하다가 짝수값과 홀수값에 주목했다.

 

순간이동을 했을때 이동한칸 x 2이므로 무조건 짝수칸에 도착하게 된다. 

즉 짝수칸만이 순간이동으로 도착할수 있고

홀수칸에 도달하려면 이전칸인 짝수칸에서 +1칸 이동할수 밖에 없다.

 

5000 -> 2500

2500 -> 1250

1250 -> 625 

625 -> 624  // 625는 홀수이므로 순간이동으로 도달할수 없는칸이다. 이전칸인 짝수칸에서 +1칸 이동 

624 -> 312

312 -> 156

156 -> 78

78 -> 39 

39 -> 38 // 39는 홀수칸 

38 -> 19 

19 -> 18 // 19는 홀수칸 

18 -> 9

9 -> 8 // 9는 홀수칸 

8 -> 4

4 -> 2

2 -> 1

1 -> 0 // 1은 홀수칸 

 

총 다섯개의 홀수칸이 있었으므로 다섯번 이동했다.