[programmers] 마법의 엘리베이터

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

프로그래머스

 

---------------------------------------------------핵심 알고리즘-----------------------------------------------------

 

모든 경우의 수를 탐색하여 최소를 찾아냈다. brute force

각 인덱스의 숫자마다 10에서 빼는게 빠른지, 0에서 더하는게 빠른지를 생각해보면 간단하다.

예를 들어, 6이면 -1*6으로 6번 사용할지, +1*4-10*1로 5번 사용할지를 고려한다.

 

------------------------------------------------------풀이----------------------------------------------------------

 

make_storey_to_s()로 주어진 storey를 일의자리수 부터 vector s에 저장한다.

900이라면, 900+100-1000이 900-100*9보다 적게 사용하는 것처럼, carry가 생기면 더 좋은 상황을 생각해 실제 length보다 1 크게 만든다. 그러기 위해 0을 마지막에 추가한다.

 

find_min()에서 현재 인덱스(cur_idx)의 값을 기준으로 10을 만들지 0을 만들지 분기를 나누어 체크한다.

마지막 인덱스를 체크하는 경우, 현재 answer에 저장된 최솟값보다 작은지 판단에 업데이트 한다.

#include <string>
#include <vector>

using namespace std;

int answer;
vector<int> s;

void make_storey_to_s(int storey){
    while(storey){
        s.push_back(storey % 10);
        storey /= 10;
    }
    s.push_back(0); // 맨 마지막에 carry가 생겨 올라가는경우를 위해.
    // 즉, 600이면 (+100*4-1000*1)이 (-100*6)보다 적음.
}

// 현재 s의 인덱스 cur_idx, 아래서 더했다면 발생할 carry
// 현재까지의 돌 사용 횟수 used
void find_min(int cur_idx, int carry, int used){
    // 경우의수 제거용 - 이미 사용 횟수가 정답보다 크면 종료
    if(used >= answer){
        return;
    }
    
    // 모든 값에 대해 어떻게 할지(더할지뺄지) 결정했으면, 총 사용 횟수 비교
    // 0이 목적지이므로 마지막 인덱스는 무조건 빼야함.
    if(s.size()-1 <= cur_idx){
        int cur_val = s[cur_idx] + carry;
        if(used + cur_val < answer){
            answer = used + cur_val;
        }
        return;
    }
    
    // 현재 인덱스의 값에 대해 사용 횟수 결정.
    int cur_val = s[cur_idx] + carry;
    if(cur_val >= 10){
        cur_val %= 10;
        carry = 1;
    }
    else{
        carry = 0;
    }
    // 더할 경우
    find_min(cur_idx+1, carry+1, used+(10-cur_val));
    // 뺄 경우
    find_min(cur_idx+1, carry, used+(cur_val));
}

// +-10^c(c>=0) 형태의 정수들. -1, +1, -10, +10, -100, +100 ,...
// 현재 층 수에 버튼에 적힌 값을 더한 층으로 이동.(돌 한 개 사용)
// 단, 더한 결과가 0보다 작으면 움직이지 않음. 0이 가장 낮은 층.
// 최소한의 버튼을 눌러 0층으로 이동할 때 최소의 마법의 돌의 개수=?
int solution(int storey) {
    answer = 200'000'000;
    // storey를 vector로 변경(뒤에부터 거꾸로 저장)
    make_storey_to_s(storey);
    
    // 각 자리수마다 10에서 빼서 만드는게 빠른지, 0에서 더해서 만드는게 빠른지 비교
    // 6 = 10-4 = 0+6 따라서 -4를 하는게 나음.
    // 이걸 낮은자리에서부터 경우의수 탐색
    find_min(0, 0, 0);
    return answer;
}

 

--------------------------------------------------------후기--------------------------------------------------------

 

모두 탐색해서 경우의 수를 비교하면 되겠다는 생각이 먼저 들었다.

storey가 100'000'000 이하이므로, 각 자릿수를 생각하면 최대 depth가 9라고 생각했기 때문이다.

실제로 이 부분에서 문제는 없었는데, 고려하지 못한 점은 600이면 600 + 100*4 - 1000*1 이 방식으로 1000을 만들어 빼는 방식이 600 - 100*6로 하는 방식보다 적게 돌을 사용한다는 점이다.

즉, 이미 주어진 length보다 더 길게 만들어 사용하는 것이 더 편할 수 있다는 것을 놓쳤다.

다음부터는 조금 더 차분히 생각해보는 시간이 필요하다...