문제 설명
K연구소는 K칸 앞으로 점프하거나 (현재까지 온 거리)*2 만큼 순간이동하는 아이언 슈트를 만들었다고 한다. 이 아이언슈트는 K칸 점프하면 K칸 건전지가 닳는다. 순간이동에서는 닳지 않는다. 0부터 N까지 가려고 할 때 가능한 최소한의 건전지 사용량을 구하라
문제 풀이
첫 번째 접근
문제를 보자마자 DP라고 생각했다. 이런 종류의 DP 문제를 많이 봐왔기 때문이다. 그렇기에 배열을 설정해주고 위치 1에는 1을 넣은 후 1부터 n까지 점프할 경우와 순간이동할 경우의 최소 베터리 사용량을 구해줬다. 이렇게 하면 마지막 값에 최소 사용량이 나온다.
이렇게 풀어서 문제를 통과하나 싶었으나... 이 문제에는 효율성 테스트가 있다는 사실! ㅎㅎ... 숫자 N이 무려 1억개나 된다. 그렇기에 당연히 효율성 테스트에 걸려서 틀렸다.
두 번째 접근
그렇다면 어떻게 해야 하나? 2를 곱해주는 걸 보니 나누기를 하는 거 같은데... 다른 사람의 풀이를 참고하니 top-down 방식을 사용하는 풀이가 있었다.
n에서부터 시작해서 만일 순간이동을 할 수 있으면 2로 나눠준다. 왜냐하면 n이 4일 경우 이미 1칸 점프했다는 의미이니 1*2로 움직일 수 있고 이 값은 4/2이기 때문이다. 만일 n이 홀수이면 1칸을 앞으로 움직인다는 의미로 n에다가 1을 빼주면 된다. 이때는 베터리를 사용하니 ans를 1더해주면 된다.
예상보다 간단한 문제였으나 문제의 조건을 제대로 보지 못해 틀렸던 문제다. 다음부터는 문제를 꼼꼼히 확인하고 조건을 본 후 내 알고리즘이 시간 초과까지 완벽하게 통과를 할지 계산을 해보자.
코드
Java
while(n != 0 ){
if(n%2 == 0){
n /= 2;
}else{
n--;
ans++;
}
}DP(테스트는 통과, 효율성 테스트는 통과 X)
/*
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
// arr[0] = 0;
for(int i=1; i<n; i++){
//순간이동
//현재까지 온 거리
int length = i;
//i에다가 2를 곱해서 순간이동으로 갈 수 있는 거리가 n안에 있을 때만
if(i*2 <= n){
if(dp[i*2] == 0){
dp[i*2] = dp[i];
}else{
dp[i*2] = Math.min(dp[i], dp[i*2]);
}
}
//점프
if(dp[i+1] == 0){
dp[i+1] = dp[i] + 1;
}else{
dp[i+1] = Math.min(dp[i+1], dp[i]+1);
}
}
ans = dp[n];*/링크
프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/12980
참고 풀이
유사 문제
