문제링크

문제링크

문제 설명

제한사항

입출력 예

입출력 예 설명

풀이

1. 문제의 핵심은 "목표치까지 도달하기위한 최솟값"이니 bfs를 먼저 떠올려보자
2. 나는 매번 1의 자릿수를 통해 각 자릿수 버튼을 얼마나 눌러야할지 최종 결과값에 계속 더할려고한다.
3. 1의 자리만 떼놓고 판단해도 되는게, 어차피 문제에서 주어지는 storey는 1억이내의 자연수다.
   3-1 여기선 1억이라는 숫자의 크기보다, 최대 9자리 자연수가 올 수 있다고 받아들일 수 있다.
   3-2 만약, 1의자리가 5보다 크면? 반올림을 하면된다.
   3-3 1의자리가 5보다 작으면? 내림을 하면 된다.
   3-4 1의자리가 5라면? 반올림, 내림 둘 다를 우선순위 큐에다가 넣어보자.
4. 그렇게 최솟값이 나오면 바로 리턴하면 된다.
   4-1 주의할 점은 현재 value가 0이 되었다고 해서 그게 최솟값이 아닐 수 있다는 것이다.
   4-2 그래서 큐가 빌때까지 계속 로직을 돌려서 최솟값을 갱신해나가야한다.

처음에는 이 로직을 bfs가 아닌 구현문제라고 생각했다.

전체 로직은 비슷하지만, 1의 자리가 5일때는 그냥 내림하는게 최솟값일 줄 알았다.

그래서 테스트케이스도 대부분 통과했지만, 딱 3개가 통과를 못하는것이다 ㅜㅜ

질문하기 코너에서 반례를 몇개 주워보는 과정에서, 내 로직을 딱 관통하는 반례를 발견했고 코드를 엎어야겠다..라는 생각밖에 들지 않았다 ㅋㅋㅋ

그리하여 bfs를 바로 채택하고 통과!

코드

import java.util.*;
class Ev {
    int now;
    int depth;
    Ev(int now, int depth) {
        this.now = now;
        this.depth = depth;
    }
}
class Solution {
    public int bfs(int storey) {
        Queue<Ev> q = new LinkedList<>();
        q.add(new Ev(storey, 0));        
        int result = 10000000;
        while(!q.isEmpty()) {
            Ev ev = q.poll();
            int now = ev.now;
            int level = ev.depth;
            if(now == 0) {
                if(result > level)
                {
                    result = level;
                }
                continue;
            }
            int num = now % 10;
            if(num > 5) { //5보다 크면 걍 반올림
                q.add(new Ev(now / 10 + 1, level + 10 - num));
            }
            else if(num == 5) {
                q.add(new Ev(now / 10, level + num)); //내림
                q.add(new Ev(now / 10 + 1, level + 10 - num)); //반올림
            }
            else {
                q.add(new Ev(now / 10, level + num));                
            }
        }
        return result;
    }
    public int solution(int storey) {
        int answer = bfs(storey);
        return answer;
    }
}