백준 - 1038 감소하는 수(JAVA)

문제 링크

---

풀이

처음에는 브루트포스, dp 등 다양한 방법으로 시도해보았으나 시간초과가 발생해 포기하고 있던 문제였다. 그러다 FIFO 구조인 queue를 사용하는 방법이 떠올라 아래와 같이 문제를 풀어냈다.

1. 우선 한 자리 수는 모두 감소하는 수 이므로 queue에 삽입한다.
2. 10번째 수 부터 queue에 있던 값을 차례로 꺼내 아래의 연산을 시작한다.
   2-1. 꺼낸 수에 10을 곱한 수를 x라고 하자.
   2-2. 0부터 (꺼낸 수 % 10 - 1) 까지 반복문을 돌려 x에 더하면 이 값들 하나하나가 모두 감소하는 수가 된다.
   ex) 큐에서 꺼낸 수가 86인 경우 -> 860, 861 ... 864, 865 모두 감소하는 수!
   2-3. 위의 연산을 n번째 까지 수행하면 다음에 push할 수를 출력하고 return한다.
3. 가장 마지막에 검사한 수(위의 예시로 따지자면 865)만 큐에 push한다.

주의할 점

• 출력이 9876543210까지 가능하므로 출력할 변수는 int가 아닌 long타입으로 선언할 것
• queue가 비게 되면 9876543210 이 이미 출력된 상태! -> -1 을 출력하고 return
• push할 수가 3210과 같이 끝자리 수가 0이라면 해당 수를 활용한 감소하는 수는 없으므로 push 하지 않는다.
  ex) 3210 x 10은 32100이고, 해당 수에는 어떤 한 자리 수를 더하더라도 감소하는 수가 될 수 없다.

---

코드

import java.util.*;

public class Main {

    static Scanner scan = new Scanner(System.in);

    static int n;
    static Queue<Long> q = new LinkedList<>();


    public static void input() {
        n = scan.nextInt();
        for (int i = 0; i <= 9; i++) {
            q.add((long) i);
        }
    }

    public static void solve() {
        if (n <= 10) {
            System.out.println(n);
            return;
        }

        int i = 10;
        while (true) {

            q.remove();

            if(q.isEmpty()){
                System.out.println(-1);
                return;
            }

            long next = 0;

            for (int j = 0; j < q.peek() % 10; j++) {
                next = (long) q.peek() * 10 + j;

//                System.out.println(q);

                if (i++ >= n) { // 시도 횟수가 n과 같아지면 다음 감소하는 수(next)를 출력
                    System.out.println(next);
                    return;
                }

                if (next % 10 != 0) // 끝자리가 0인 경우 해당 수를 활용한 감소하는 수는 없으므로 push 하지 않음
                    q.add(next);
            }

        }

    }

    public static void main(String[] args) {

        input();
        solve();

    }
}

결론

완전탐색 사용 시 시간초과가 발생하고, n번째까지 감소하는 수의 갯수를 구하는 문제가 아니라 n번째 감소하는 수를 구하는 문제였기에 dp를 사용하다 풀이에 실패했다.

queue를 사용하는 방법과 같이 열린 생각으로 다양한 접근법을 애써 고민해보려 하는 것이 중요한 것 같다.