문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12980
문제 설명
- k칸을 점프하는 데는 k만큼 건전지를 사용
- 현재까지 이동거리*2 위치로 순간이동 하는 것은 건전지 사용 안함
n만큼 이동하고 싶을 때 최소한의 건전지 사용량을 반환
1차 시도
def solution(n):
return bin(n)[2:].count('1')이건 코딩 테스트가 아니라 생각싸움같음.... 이게 뭔... 아닌가 코드를 효율성 있게 짜는 방법도 되니까 코딩테스트라고 할 수 있나..
암튼 키포인트는 n//2만큼에 도달하고 순간이동하는 것이다.
그리고 n이 홀수면 마지막에 +1을 해줘야하고.
근데 생각해보니 재귀로 가능할 것 같다는 생각이 들었다.
그래서 예시로 생각해보니, 6 위치에 도달하기 위해서는 일단 3만큼 도달하고 순간이동을 하면 되는거였고, 3만큼 도달하기 위해선 2(3//2)만큼 도달하고 +1하면 되는거고, 2만큼 도달하기 위해선 1(2//2)만큼 도달하고 순간이동하면 되는거고, 1에 도달하기 위해선 1칸을 점프하면 되는거다.
어? 이거 걍 이진수 구해서 1 갯수 세면 되는거잖아?
그래서 bin으로 n을 2진수로 변환하고 1 갯수 세서 반환하면 끝.
정리
- 문제를 풀 때는 무작정 코드 작성으로 돌진하는 게 아니라 문제를 해석하는 게 가장 중요한 듯 싶다. 물론 이런 문제가 얼마나 나올까 싶긴 하다만
