DFS로 풀 수 있는 문제다.
더 최적화를 해서 그리디로 O(N)에 풀 수도 있지만,
DFS의 풀이로 꽤 간편하고 약간은 신박하게 풀 수 있어 들고왔다.
(N: stroey의 자릿수)
stroey 를 0으로 변환하기 위해서는
마지막 자리의 숫자를 먼저 처리함으로써
두 가지 간선이 존재하도록 할 수 있다.
A. 마지막 자리의 숫자를 버리는 경우
B. 마지막 자리의 숫자를 올리는 경우
A와 B를 진행하고 나서 마지막 0은 더이상 필요없기 때문에
과감하게 지워버리자.
시간복잡도는 두 가지로 분석할 수 있다.
N을 stroey의 자릿수라고 하면 O(2^N)이 되고,
N을 stroey의 값이라고 하면 O(logN)이 된다.
#include <string> #include <vector> using namespace std; int solution(int x) { if (x/10 == 0) return min(x, 10-x+1); return min(solution(x/10)+x%10, solution(x/10+1)+10-x%10); }
이게 제일 잘 푼 풀이가 아닐까 싶다.
괜히 그리디로 이것저것 복잡하게 풀 필요가 없는 문제다.