프로그래머스 – 마법의

첫 번째 질문을 읽은 후 바로 BFS입니다! bfs로 인코딩하고 싶었습니다. Wording이 얼마 전에 비슷한 문제를 겪었기 때문에 더욱 그랬습니다(아래 첨부). 잘 읽었습니다

100까지 위의 숫자 외에도 1000, 10000까지 올라가는 것이 가능했습니다. 지정된 숫자의 자릿수까지만 bfs를 실행했지만 38점만 얻었습니다.

나는 bfs가 옳다고 당연하게 여겼기 때문에 내 코드가 어디에서 잘못되었는지 알 수 없었습니다. 이 해석이 잘못된 것입니까? 라고 생각했을 때는 이미 늦었다. 비슷한 문제를 해결했지만 바로 해결책을 찾을 수 없어서 안타깝습니다. 시간 복잡도를 계산하는 것은 여전히 ​​어려웠습니다. 시간 복잡성으로 인해 bfs가 불가능하다는 것을 즉시 알아차렸어야 합니다.

요약하면 이 문제는 욕심 많은 알고리즘입니다. 잘하면 DP로 풀 수 있을 것 같다. 힌트는 10의 거듭제곱으로 주어졌습니다. 예를 들어 숫자 2001이 들어왔을 때 마지막 1의 자릿수 때문에 방법이 다릅니다. 즉, 2000 또는 2010을 만들기 위해 숫자 1을 증가시킬 것인지 감소시킬 것인지를 결정하는 것이 핵심입니다. 그리고 문제는 5일 때인데 낮춰야 할지 올려야 할지 모르겠다.

5가 되면 무조건 오르는 부분과 내리는 부분을 모두 계산하여 낮은 숫자를 반환합니다.

비슷한 문제 https://tigerfrom2.13

https://tigerfrom2.62

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

int solution(int storey) {
    int answer = 0;
    int answer2 = 0;
    int init = storey;
    while(storey != 0){
        int tmp = storey % 10;
        if(tmp <= 5 ){ // 무조건 내림
            answer += tmp;
            storey = storey / 10;
        }
        else if(tmp > 5){ // 무조건 올림
            answer += (10 - tmp);
            storey = storey / 10 + 1;
        }
    }
    
    storey = init;
    while(storey != 0){
        int tmp = storey % 10;
        if(tmp < 5 ){ // 무조건 내림
            answer2 += tmp;
            storey = storey / 10;
        }
        else if(tmp >= 5){ // 무조건 올림
            answer2 += (10 - tmp);
            storey = storey / 10 + 1;
        }
    }
    if(answer > answer2)  return answer2;
    else return answer;
}