<Programmers> 점프와 순간 이동

이 문제를 접했을 때 재귀 함수로 하면 되지 않을까?라고 생각을 하였다. 2씩 곱해주다가 N값보다 커지면 -1을 해주고 다시 2를 곱해주는 방식으로 정확히 N이 나올 때까지 하는 것이다.

결과적으로 재귀함수로 작성하는데 실패했다. 너무 복잡하고 생각대로 풀리지 않았다. 

 

다른 사람들의 풀이를 찾아봤는데 너무 간단하게 코딩을 하는 방법이 있었다.

나는 지금까지 bottm-up방식으로 0 부터 N까지 가는 방법으로 할려고 했다. 하지만 top-down 방식으로 하면 더욱 쉽게 풀린다는 것을 알게되었다.(N->0)

 

2로 나눠지면 2로 나누고, 안나눠지면 -1을 하고 하는 방식으로 완전히 bottom-up방식의 반대로 하면 된다.

 

 

[참고한 풀이]

https://velog.io/@hyeon930/프로그래머스-점프와-순간-이동-Java

[프로그래머스] 점프와 순간 이동 (Java)

 

..이것보다 더 간결한 방법도 있다. 이 진수로 바꿔 1의 갯수를 count하는 것이다!

왜냐하면 일단 0->1은 어떤 경우에 수든 무조건 하므로 배터리는 1을 소모한다.(이진수의 1의 갯수는 1) 즉, 1번만 배터리를 소모하고 나머지는 전부다 순간이동 한다고하면 1의 개수는 무조건 1개이다. 그리고 배터리를 소모할때마다 이진수의 1이 더해지므로 1의 갯수가 늘어난다. 즉 1의 개수가 배터리 소모량이다.

 

Ex)

N=8인 경우.

1. 0->1 로 배터리 1소모(0000->0001)

2. 1->2 로 순간이동(0001->0010)

3. 2->4로 순간이동(0010->0100)

4. 4->8로 순간이동(0100->1000)

 

배터리 소모 횟수=1의 갯수 =1

 

N=6인 경우,

1. 0->1 로 배터리 1소모(0000->0001)

2. 1->2 로 순간이동(0001->0010)

3. 2->3로 배터리 1소모(0010->0011)

4. 3->6로 순간이동(0011->0110)

 

배터리 소모 횟수=1의 갯수=2