[프로그래머스] 점프와 순간 이동 c++

https://programmers.co.kr/learn/courses/30/lessons/12980 정말 이런 유의 아이디어 문제는 어렵다. 문제의 키포인트는 최대한 순간 이동을 많이 사용하는 것 연료를 적게 사용해야 되니 처음에 DFS로 풀어보려다가,, 흠 이게 N이 작으면 되는데 N이 10억이면 절대 할 수가 없다. A4에 끄적이다가 발견한 아이디어, 실제로 답도 이렇더라 6이면 1 -> 2 -> 4 -> 8 안되고 그럼 1 -> 2 -> 3 > 6이 된다. 이걸 반대로 생각하면 6 -> 3 순간 이동 3은 홀수이기에 나눌 수 없으니 1을 빼줘서 2를 만들어준다 그러면 6 -> 3 -> 2 2는 짝수이기에 나누기 1을 해준다. 순간 이동 6 -> 3 -> 2 -> 1 1은 홀수이기에..........

원문링크 : [프로그래머스] 점프와 순간 이동 c++