문제

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

풀이

시도 1

점화식을 이용해서 푸려고 그림으로 그려보니 두가지 규칙을 찾게 되었다. n개의 칸이 짝수면 n+1개의 칸은 n개를 갔을때의 건전지 + 1개가 소요된다. 그리고 n개의 칸이 2의 제곱승이면 1이 된다.

  • dp[1] = 1 (2^0)
  • dp[2] = 1 (2^1)
  • dp[3] = dp[2] + 1 = 2
  • dp[4] = 1 (2^2)
  • dp[5] = dp[4] + 1 = 2
  • dp[6] = 2
  • dp[7] = dp[6] + 1 = 3
  • dp[8] = 1 (2^3)
  • dp[9] = dp[8] + 1 = 2

그리고 쩜프는 2의배수씩 순간이동하기 떄문에 다음에 오는 dp[10]은 결국 dp[5]에서 순간이동하는 것 과 같으므로 dp[5]와 배터리가 같다

  • dp[10] = dp[5]

규칙을 정리하니 다음과 같은 점화식을 얻을 수 있었다.

  • n = 홀수인경우 : dp[n] = dp[n-1] + 1
  • n = 짝수인 경우 : dp[n] = dp[n/2]
  • dp[0] = 0
  • dp[1] = dp[0] + 1 = 1
  • dp[2] = dp[1] = 1
  • dp[3] = dp[2] + 1 = 2
  • dp[4] = dp[2] = 1
  • dp[5] = dp[4] + 1 = 2
  • dp[6] = dp[3] = dp[2] + 1 = 2
  • dp[7] = dp[6] + 1 = 3
  • dp[8] = dp[4] = dp[2] = dp[1] = 1
  • dp[9] = dp[8] + 1 = 2
  • dp[10] = dp[5] = dp[4] + 1 = dp[2] + 1 = 2
solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def solution(n):
    dp = [0 for _ in range(0, n)]
    dp[0], dp[1], dp[2] = 0, 1, 1
    for i in range(3, n):
        if i % 2 == 0:
            dp[i] = dp[int((i + 1) / 2)]
        else:
            dp[i] = dp[i - 1] + 1
        print(i, dp)
    return dp[-1]

시도 2

시도 1이랑 비슷한데 접근을 잘못했었다. 쉬운문제였는데 너무 복잡하게 생각한게 탓이었다…. 예를들어 5,000으로 생각하면 다음과 같다

  • flag = 1 (한칸은 무조건 전진해야하므로)
  • 5000 / 2 = 2500
  • 2500 / 2 = 1250
  • 1250 / 2 = 625
  • 625 / 2 = 312 … 나머지 있으므로 flag += 1
  • 312 / 2 = 156
  • 156 / 2 = 78
  • 78 / 2 = 39
  • 39 / 2 = 19 … 나머지 있으므로 flag += 1
  • 19 / 2 = 9 … 나머지 있으므로 flag += 1
  • 9 / 2 = 4 … 나머지 있으므로 flag += 1
  • 4 / 2 = 2
  • 2 / 2 = 1
  • return flag = 5

난이도 있는 점화식을 계속 풀었어서 그런지 문제 자체를 너무 복잡하게 생각했었던 것 같다. 손으로 써보는 버릇을 들여야 겠다.

solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def solution(n):
    dp = [0 for _ in range(0, n)]
    dp[0], dp[1], dp[2] = 0, 1, 1
    for i in range(3, n):
        if i % 2 == 0:
            dp[i] = dp[int((i + 1) / 2)]
        else:
            dp[i] = dp[i - 1] + 1
        print(i, dp)
    return dp[-1]

다른사람풀이

또 곰곰히 보니까 2진수로 전환해서 1이 남은 수랑 똑같다… 이진수로 변환해서 1을 체크하면 더 쉽게 풀수 있었을텐데 아쉬움이 든다. 나눗셈하면서 2진수 생각을 왜 못했을까 🤣

solution.py 
1
2

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