[프로그래머스] 마법의 엘리베이터 자바 (Level 2) DFS 완전탐색

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/148653

1. 문제 요약

• 주어진 층수 storey를 10의 n제곱값을 더하거나 빼서 0을 만든다.
• storey를 0으로 만드는데 필요한 최소 횟수를 구한다.

2. 핵심 아이디어

• DFS 방식으로 0까지 차감 or -부터 0까지 증가하는 두 가지방식으로 탐색 및 비교하기.

3. 풀이 코드

/**
     * @param storey : 현재 층
     * @return 0층까지 가기위한 최소 횟수
     */

    int minValue = Integer.MAX_VALUE;
    //버튼 누르면 현재 층 + 10^n (n 은 정수) 로 이동. 결과값 < 0 이면 이동하지 않음. 0층 밑은 없음.
    public int solution(int storey) {
        //양수버전과 음수버전 비교해서 더 작은값이 최소값
        dfs(storey, 0);
        return minValue;
    }

    void dfs(int storey, int cnt){
        if(cnt > minValue) return;

        if(storey == 0){
            minValue = Math.min(minValue, cnt);
            return;
        }

        int digit = storey % 10; //1의 자리
        int next = storey / 10;

        // 1. 내려감
        dfs(next, cnt + digit);

        // 2. 올림
        dfs(next + 1, cnt + (10 - digit)); // 대상을 반올림하여 처리하는데 필요한 횟수. next + 1 : 올림처리했으므로 자리 1 추가.
    }

 

4. 회고 및 느낀점

• dfs를 사용해야겠다 까지는 좋았지만 상세로직을 만들어 내는 데는 실패. -> GPT를 통해 dfs 내부코드 구현..
• GPT를 통해 풀이코드를 놓고 보면은 크게 어렵지 않지만, 이 내용을 구상해내는 것이 어려웠고 여전히 어렵다.
• 이해한 내용을 코드로 풀어내는 것에 좀 더 연습이 필요한 것 같다.
• GPT없이도 문제를 해결할 수 있도록.