[프로그래머스] 점프와 순간 이동(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "점프와 순간 이동" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 아이언 슈트를 착용한 사용자가 거리 N만큼 이동하려고 할 때 필요한 최소한의 건전지 사용량을 구하는 것이 목적입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크 : 

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

프로그래머스

문제 개요

"점프와 순간 이동" 문제에서는 아이언 슈트를 착용한 사용자가 거리 N만큼 이동하려고 할 때 필요한 최소한의 건전지 사용량을 구하는 것이 목적입니다. 아이언 슈트는 한 번에 K 칸을 점프할 수 있으며, 순간이동을 하면 현재까지 온 거리의 두 배로 이동할 수 있습니다. 점프는 건전지를 소모하지만, 순간이동은 건전지 소모가 없습니다.

문제 해결 전략

이 문제를 해결하기 위한 핵심 전략은 점프를 최소화하고 순간이동을 최대화하는 것입니다. 건전지 사용량을 줄이기 위해선 목적지에 도달하기 위해 필요한 점프 횟수를 최소로 줄여야 합니다.

구현 단계:

1. 목적지에서 시작하기: 목적지에서 시작하여 출발점으로 거슬러 올라가는 방식으로 문제를 접근합니다.
2. 순간이동의 효율적 사용: 현재 위치가 짝수이면 순간이동을 합니다. 순간이동은 현재 위치를 2로 나누는 것과 같습니다.
3. 점프의 최소화: 현재 위치가 홀수일 때만 점프를 사용합니다. 점프는 건전지 사용량을 1만큼 증가시킵니다.
4. 반복 실행: 현재 위치가 0이 될 때까지 위의 과정을 반복합니다.

코드 구현

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// 재귀 함수로 순간이동과 점프를 처리하는 함수
void DFS(int n, int &ans){
    // 재귀의 기본 조건, n이 0 이하가 되면 함수를 종료
    if(n <= 0){
        return;
    }
    // 순간이동: 현재 위치가 짝수일 경우
    if(n % 2 == 0){
        DFS(n/2, ans); // 현재 위치를 2로 나누어 순간이동
    }
    // 점프: 현재 위치가 홀수일 경우
    else{
        ans += 1; // 점프는 건전지 사용량을 1 증가시킴
        DFS(n - 1, ans); // 현재 위치에서 1을 빼어 점프
    }
}

// 주어진 목적지까지 이동하는데 필요한 최소 건전지 사용량을 계산하는 함수
int solution(int n)
{
    int ans = 0; // 건전지 사용량을 저장할 변수

    // 첫 번째 호출
    if(n % 2 == 0){
        DFS(n/2, ans);
    }
    else{
        ans += 1;
        DFS(n - 1, ans);
    }
    return ans; // 계산된 최소 건전지 사용량 반환
}

코드 설명

• 주어진 목적지에서 시작하여, 위치가 0이 될 때까지 순간이동과 점프를 결정합니다.
• 현재 위치가 짝수일 경우 순간이동을 선택하고, 홀수일 경우 점프를 선택합니다.
• 점프를 할 때마다 건전지 사용량을 1 증가시킵니다.
• 최종적으로 계산된 건전지 사용량을 반환합니다.

결론

"점프와 순간 이동" 문제의 해결은 순간이동을 최대한 활용하여 점프 횟수를 줄이는 데 있습니다. 이 접근 방식은 건전지 사용량을 최소화하는 최적의 해결책을 제공합니다.