[C++] 프로그래머스 마법의 엘리베이터

마법의 엘리베이터 문제 바로가기

사용 알고리즘

• 완전 탐색

 

풀이

경우의 수가 4가지 존재한다.

• 이전 층 영향 있음 (자리 올림)
  • 현재 층에서 올라가기
  • 현재 층에서 내려가기
• 이전 층 영향 없음
  • 현재 층에서 올라가기
  • 현재 층에서 내려가기

이전 층에 영향 없으면 눌러야 되는 버튼 수를 그대로 더하면 된다.

하지만 이전 층에 영향이 있으면 자리올림 때문에 버튼 수를 1을 더해준다.

 

풀이 코드

#include <bits/stdc++.h>

using namespace std;

int ans = 1e9;
string elevator;

// 캐리 여부, 현재 위치, 버튼 누른 수
void dfs(bool carry, int depth, int cnt) {
    // 종료 조건
    if(depth == -1) {
    	// 캐리
        if(carry) cnt++;
        
        if(cnt < ans) 
            ans = cnt;
        return;
    }
    
    // 현재 층
    int btn = elevator[depth]-'0'; 
    
    // 자리올림
    if(carry) {
        dfs(1, depth-1, cnt + (10 - (btn+1))); // 올라감
        dfs(0, depth-1, cnt + (btn+1)); // 내려감
    }
    else {
        dfs(1, depth-1, cnt + (10 - btn)); // 올라감
        dfs(0, depth-1, cnt + btn); // 내려감
    }
}

int solution(int storey) {
    elevator = to_string(storey);
    int n = elevator.length();
    
    dfs(0, n-1, 0); 
    
    return ans;
}

 

후기

더 똑똑하게 5를 기준으로 할 수 있었지만 엘리베이터의 길이가 짧아서 그냥 완탐으로 했다