문제 설명
OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
- 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
- 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
- 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.
위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.
제한 사항
- 숫자 N: 1 이상 10억 이하의 자연수
- 숫자 K: 1 이상의 자연수
풀이
문제를 읽고 바로 DP라고 생각했다.
간단하게 i번째 칸에 도착하는 경우는 i-1칸에서 점프한 경우와 i/2칸에서 순간이동한 경우이다.
하지만 홀수는 순간이동이 불가능하기 때문에 이를 제외하고 계산하였더니 정확성테스트는 모두 맞았지만 효율성테스트에서 시간 초과와 메모리 초과가 발생했다.
그래서 BFS로 바꿔 보았다.
거리가 1, 2인 칸까지의 건전지 사용량은 1로 쉽게 계산할 수 있기 때문에 이를 초기값으로 설정하여 BFS를 진행했다.
i번째 칸이 목적지와 같다면 현재까지의 배터리 사용량을 정답으로 설정하고 while문을 빠져나오게 하였다.
목적지가 아니라면 i+1에 건전지 1을 추가로 사용한 경우와 i*2에 건전지를 추가로 사용하지 않은 경우를 큐에 넣고 BFS를 계속하여 진행하도록 설계했다.
하지만, BFS도 시간초과에 걸렸다.
정답은 의외로 간단했다.
앞에서 설명한대로 홀수인 칸에는 순간이동이 불가능하다.
즉, 무조건 이전칸에서 1칸 점프를 해야 한다.
그리고 짝수인 칸에는 무조건 순간이동으로 도착하는 것이 건전지를 최소로 사용하는 방법이다.
따라서, 목적지 n이 0이 될때까지 짝수인 경우는 /2를, 홀수인 경우 -1을 하며 건전지 사용량을 1 증가시키며 진행하면 된다.
DP, BFS 모두 코딩테스트에 자주 적용되는 풀이법이지만, 이 경우에는 그리디로 접근하는 것이 맞았다.
글을 적으며 든 생각이지만, 최적화문제를 결정문제로 변경하는 파라메트릭 서치를 사용해도 괜찮을것 같다는 생각이 든다. → 가능 여부를 판단하는데 연산이 더 들어간다.
전체 코드
#include <iostream>
#include <vector>
using namespace std;
int solution(int n)
{
if(n == 1 || n == 2) return 1;
int ans = 0;
while(n != 0)
{
if(n % 2 == 0)
{
n /= 2;
}
else
{
n--;
ans++;
}
}
return ans;
}