Skip to main content

12980 - 점프와 순간 이동

info

풀이 키워드​

스포주의

구현 그리디


풀이 코드​

info
  • 메모리: 9340 KB
  • 시간: 0 ms
def solution(n):
    ans = 0
    while 0 < n:
        isOdd = n & 1
        n = (n - 1 if isOdd else n // 2)
        ans += isOdd
    
    return ans

풀이 해설​

DP는 시간초과가 발생하여 그리디로 접근해야 하는 문제이다.


📌 역발상하기​

0을 연산하여 n을 만든다고 생각하면 시작할때 무조건 1을 점프해야되고, 이 부분의 처리가 깔끔하지 않으므로

역으로 n에서 0으로 연산하는 발상이 필요하다.


📌 도착 지점의 특징 고려하기​

순간이동은 ×2\times 2 연산이라서, 순간이동을 한 직후의 도착 지점은 짝수이다.

이를 명제로 적용하면 다음의 2가지 논리가 참임을 알 수 있다.

  • P→QP \rightarrow Q: 순간이동을 한 직후의 도착 지점은 짝수이다.
  • ∼Q→∼P{\sim} Q \rightarrow {\sim} P: 도착 지점이 홀수라면 순간이동을 한 직후가 아니다. (= 직전에 점프했다)

따라서 n -> 0으로 진행하며, 현 지점이 짝수면 역순간이동 연산을 해주고, 홀수면 역점프 연산을 해주면 된다.

역점프할땐 배터리 비용을 합산해주는것도 잊지 말자.



warning

무지성 DP 들박 좀 하지말라고​

TL; DR: 빨리 풀고 싶어도 반드시 콜스택 깊이 계산할 것

1≤N≤1091 \le N \le 10^9 라고 쓰인거 봤는데 왜 무지성으로 DP 접근함?

최악의 경우 (1칸씩 이동 * 10^9) 라서 탑다운 dp는 재귀 깊이 10^9가 됨.

사고방식이 완탐 -> 아 재귀가 더 편하네 -> DP 접근 이거까지밖에 안되고 있음.

  1. DP 고려 -> 범위 확인 -> OK ㄱㄱ
  2. DP 고려 -> 어 범위가 좀 큰데? -> 다른 유형 고민 -> 다 안맞는 것 같은데? 로 넘어가는 것이 필요함.

2번에서 다 안맞으면 그리디로 접근하면 되고, 딱히 의심되는 유형 없으면 그리디로 바로 가는게 좋을듯.


메모​

  • 그리디 기초 문제같은 느낌
  • 체감 상 구현 난이도 1, 발상 난이도 2~3 정도였음.