[Algo] 백준 1174 줄어드는 수 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/1174

---

코드

비트마스크 이용

메모리 : 14572KB

시간 : 148ms

언어 : Java 11

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static int N;
    static int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    static List<Long> ans;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ans = new ArrayList<>();

        for (int i = 0; i < (1 << 10); i++) {
            long num = 0;
            for (int j = 0; j < 10; j++) {
                if ((i & (1 << j)) != 0) {
                    num = num * 10 + arr[j];
                    if (!ans.contains(num)) {
                        ans.add(num);
                    }
                }
            }
        }

        Collections.sort(ans);
        if (ans.size() < N) {
            System.out.println(-1);
        } else {
            System.out.println(ans.get(N - 1));
        }
    }
}

코드

dfs조합을 이용

메모리 : 14608KB

시간 : 156ms

언어 : Java 11

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static int N;
    static int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    static List<Long> ans;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ans = new ArrayList<>();
        dfs(0, 0);
        Collections.sort(ans);
        if (N > ans.size()) {
            System.out.println(-1);
        } else {
            System.out.println(ans.get(N - 1));
        }

    }

    private static void dfs(long num, int idx) {
        if (!ans.contains(num)) {
            ans.add(num);
        }
        if (idx >= 10) {
            return;
        }
        dfs((num * 10) + arr[idx], idx + 1);
        dfs(num, idx + 1);
    }
}

풀이

일단 공통적인 풀이는 다음과 같다.

1. 왼쪽부터 자리수가 감소하는 가장 큰 수는 9876543210 이다. 따라서 9876543210 보다 작은 수들 중 왼쪽부터 오름차순인 수를 찾아야 한다.
2. 조합을 만드는데, 숫자의 배열 arr가 가장 큰 수의 배열과 같다. 조합을 만들 때 idx는 왼쪽(0)에서 오른쪽 (N)으로 이동하기때문이다. idx를 선택하거나 선택하지않고 넘어가면서 계속 뒤에 작은 수들을 붙일 수 있기 때문이다. 만들어진 조합의 앞자리 수는 항상 뒷자리 수보다 크다는 것을 보장받는다.

비트마스크 : 10가지의 숫자 중 어떤 숫자를 선택할 것인지==해당 자리수의 비트가 1인지 여부이다.

//모든 경우의 수 : 2의 10제곱
  for (int i = 0; i < (1 << 10); i++) {
            long num = 0;
            //숫자 10가지 중에 무엇이 선택됐는지 볼것이다
            for (int j = 0; j < 10; j++) {
                //i와 2의 j제곱이 0이 아니면 == 해당 자리수가 1이면
                //해당 idx는 선택받았다!
                if ((i & (1 << j)) != 0) {
                    //10을 곱해 자릿수를 밀어주고, 해당 idx 더하기
                    num = num * 10 + arr[j];
                    //중복방지
                    if (!ans.contains(num)) {
                        ans.add(num);
                    }
                }
            }
        }

dfs : 평범한 조합..