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

문제

 

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

프로그래머스

 

 

문제풀이

 

완전탐색으로 풀었다. 시간 복잡도가 크므로 간단히 참고만 하시길 바랍니다.

 

0부터 150,000,000까지 모든 경우의 수를 탐색하면서 answer을 최솟값으로 갱신한다.

처음에는 100,000,000으로 두고 했는데, 57595358의 반례가 있어서 넉넉하게 바꿨다.

 

int getSum(int num) {
    int ret(0);
    while (num > 0) {
        ret += num % 10;
        num /= 10;
    }
    return ret;
}

int형의 각 자리의 숫자들을 더해 반환하는 함수이다.

 

int solution(int storey) {
    int answer(getSum(storey));

    for (int num = 0; num <= 150000000; ++num) {
        answer = min(answer, getSum(num) + getSum(abs(num - storey)));
    }

    return answer;
}

메인문이다.

answer을 각 자리를 더한 값으로 저장한다.

0부터 150,000,000까지 증가시키면서, 해당 값에 대한 getSum 값을 구한다.

그다음 해당 수에서 storey을 만드는데 누르는 버튼 횟수를 구해 더한다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int getSum(int num) {
    int ret(0);
    while (num > 0) {
        ret += num % 10;
        num /= 10;
    }
    return ret;
}

int solution(int storey) {
    int answer(getSum(storey));

    for (int num = 0; num <= 150000000; ++num) {
        answer = min(answer, getSum(num) + getSum(abs(num - storey)));
    }

    return answer;
}