Level 2 점프와 순간 이동 Python3

programmers.co.kr/learn/courses/30/lessons/12980

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

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

def solution(n):
    return bin(n).count('1')

 

풀이 과정

풀이 시간  45분

 최종 풀이를 보면, 너무 허무한 한 줄로 문제를 해결할 수 있다. 이에 반해 나는 무려 45분이나 소요했다.

그 이유는 그동안 풀어왔던 삼성 기출 문제의 풀이 방법에 익숙해져 dfs방식을 문제에 적용했기 때문이다. 결국 이 방법으로는 문제를 해결할 수 없었고 잘못 푼 코드와 자세한 과정은 아래 오답노트에 기술하도록 하겠다.

 

 이제 최종 코드에 대한 설명을 시작해보겠다.

문제의 예시들을 살펴보면, 순간 이동을 얼마나 잘 했는지에 따라 건전지 사용량을 최소화 할 수 있다는 것을 알 수 있다. 순간 이동을 하면 현재까지 온 거리 x 2의 위치로 이동하게 된다. 따라서, 처음 0의 위치에서는 순간 이동을 할 수 없고 이동한 거리가 있어 현재 위치가 > 0인 경우에 순간 이동을 할 수 있다.

문제의 예시를 보면 건전지 사용량을 최소로 하여 n에 도착하는 것에는 규칙이 숨어져있다. n을 2로 계속 나누어 보면서 나머지가 1인 경우에는 점프를 해야하고, 나누어 떨어지는 경우에는 순간 이동을 통해 움직일 수 있다는 것이다.

 

 예를 들어, 문제 예시에 나온 N = 5인 경우를 살펴보자. 

먼저, 5를 2로 나눈 나머지는 1 이므로 1 칸 점프 한다. 5를 2로 나눈 몫에서 다시 2를 나눈다. 즉, 2 % 2 = 0 이므로, 순간 이동을 한다. 다시 2를 2로 나눈 몫인 1을 2로 나눈다. 나머지가 1이므로 1 칸 점프 한다. 따라서, 점프는 총 2번 했으므로 건전지 사용량이 2로 가장 작아 답이 된다.

 

이렇게 2로 계속 나눠 가며 나머지를 통해 점프를 할 지, 순간 이동을 할 지 정하면 되는데, 이 과정이 n의 2진수를 구하는 과정과 같다는 것을 알 수 있다. 즉, 다시 예시로 돌아가 N = 5인 경우, 5의 2진수는 101(2)이다. 1의 개수가 바로 점프를 하여 사용된 건전지량인 것이다.

 

 따라서, 이를 코드로 나타내면 다음과 같다.

def solution(n):
    return bin(n).count('1')

 파이썬은 이진수 반환하는 bin과 문자열이나 배열에서 특정 값의 개수를 반환하는 count함수가 내장되어있다. bin과 count에 대해서는 아래 참고 부분을 참고하면 좋겠다.

 

---

오답 노트

DFS를 활용한 잘못된 풀이

ans = 0

def go(now, k, n):
    global ans
    if now >= n:
        if now == n and k < ans: ans = k
        return
    for i in range(1, n+1):
        go(now + i, k + i, n)
    if now > 0:
        go(now * 2, k, n)

def solution(n):
    global ans
    ans = n
    go(0, 0, n)
    return ans

 위 코드가 내가 처음 작성한 코드이다. 나는 모든 경우의 수를 탐색하는 dfs를 활용 해 최소 소모 건전지량을 구하려 했다.

 

코드 실행을 해보면 예제 1, 2는 통과하는데 예제 3을 실행하다가 위와 같이 RecursionError가 발생했다.

 

 

RecursionError

 검색을 해보니, 파이썬에서는 최대 재귀 깊이(maximum recursion depth)가 1,000으로 정해져 있다고 한다. 따라서 예제 3의 경우 N=5000인 경우 RecursionError가 발생한 것이었다.

따라서, 위와 같이 dfs를 활용하는 방법으로는 문제를 해결 할 수 없다.

 

 

---

참고

• 2021/01/21 - [Python/내장 함수] - count, len

count, len

• 2021/01/21 - [Python/내장 함수] - bin, oct, hex

bin, oct, hex