[BOJ] 1174.줄어드는 수

in Dev. Log on Algorithms Solutions

백준 알고리즘 문제 풀이

해당 문제는 백트래킹 방식으로 풀어보았습니다.

링크 : image

1. 문제

문제 보기
시간 제한메모리 제한
2 초128 MB

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력(Input)

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력(Output)

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

2. 문제 풀이

이 문제는 백트래킹을 활용하여 풀어보았다.

오늘은 포스트를 작성 할 수 없어서 추후 업데이트 하겠다.

백트래킹 방식

비트마스킹 방식

그럼 이것을 활용하여 코드로 표현해보자. 또한 비트마스킹으로도 풀이가 가능하기 때문에 함께 소스코드를 작성해 본다.

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

public class Decreasenum_1174 {
    public static int[] num = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    public static ArrayList<Long> al = new ArrayList<Long>();
    public static void solutionByBitmask(int n) {
        ArrayList<Long> list = new ArrayList<Long>();
        // 2^10의 모든 경우의수를 만든다.
        for(int i = 1; i < (1<<10); i++) {
            long sum = 0;
            // 10 자리만큼 탐색
            for(int j = 0; j < 10; j++) {
                // i가 0^2, 1^2, 2^2, .. , j^2 보다 크다면
                // i에 해당하는 비트가 각각 어느위치에 비트를 가지고 있는지 체크
                // if문을 만족한다면 해당 자릿수가 만족한다는 것이므로 sum*10 + num[j]를 추가.
                if( (i & (1 << j)) > 0 ) {
                    sum = sum * 10 + num[j];
                }
            }
            list.add(sum);
        }

        Collections.sort(list);
        if(n > list.size()) {
            System.out.println("-1");
            return;
        }
        System.out.println(list.get(n - 1));
    }

    public static void solutionByRecursive(long sum, int idx) {
        if(!al.contains(sum)) {
            al.add(sum);
        }
        if(idx >= 10) {
            return;
        }
        solutionByRecursive( (sum * 10) + num[idx], idx + 1);
        solutionByRecursive(sum, idx + 1);
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());

        int result = 0;
        if(result == 0) {
            solutionByBitmask(N);
        } else {
            solutionByRecursive(0, 0);
            al.sort(null);
            if(N > 1023)
                System.out.println("-1");
            else
                System.out.println(al.get(N - 1));
        }
    }
}