[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)1038번, 감소하는 수

문제 링크

1038번: 감소하는 수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 가장 큰 자릿수부터 작은 자릿수까지 감소하면 감소하는 수입니다.

2. 0은 0번째 감소하는 수, 1은 1번째 감소하는 수입니다.

3. N번째 감소하는 수를 결과로 출력합니다.

4. N번째 감소하는 수가 존재하지 않을 경우 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 감소하는 수가 증가하는 개수를 기준으로 가장 가까운 자릿수를 얻어서 N번째 감소하는 수를 탐색합니다.

 

3. N번째 감소하는 수에 따른 결과를 출력합니다.

 

 

감소하는 수 가장 가까운 자릿수 얻기

 

10 : 1개(10)

20 : 2개(20, 21)

30 : 3개(30, 31, 32)

....

 

200 : 1개(210)

300 : 3개(310, 320, 321)

400 : 6개(410, 420, 421, 430, ,431, 432)

....

 

3000 : 1개(3210)

4000 : 4개(4210, 4310, 4320, 4321)

...

 

규칙을 발견할 수 있습니다.

 

200 ->  1개300 -> 10 + 20  = 3개400 -> 10 + 20 + 30 = 6개

 

3000 -> 1개4000 -> 200 + 300 = 4개

 

자신보다 자릿수가 1개 낮은 값들에서 앞자리보다 작은 값들의 합이 경우의 개수입니다.

 

가장 가까운 자릿수를 얻기 위해서

 

경우의 수를 더해가며 N보다 클 때까지 탐색합니다.

 

예를 들어

 

N = 20

 

0 ~ 9 : 9개

 

10 : 1개

 

20 : 2개

 

30 : 3개

 

40 : 4개

 

= 19개

 

50 : 5개

 

= 24개

 

N(20) ≤ 24 만족!

 

50에 자릿수를 모두 사용했을 경우 N보다 커지므로, 50으로 만들 수 있는 감소하는 수 중에 N번째 감소하는 수가 존재!

 

40까지 19개의 감소하는 수가 존재하므로 20은 50으로 만들 수 있는 첫 번째 감소하는 수

20(N) - 19(40까지의 모든 감소하는 수) = 1

 

50에서 만들 수 있는 첫 번째 감소하는 수 : 50

 

20번째 감소하는 수 : 50

 

자릿수 기준 몇 번째 감소하는 수인지 확인

 

앞자리와 자릿수를 이용해서 만들 수 있는 모든 감소하는 수 List에 저장 후

 

Collections.sort를 이용해서 오름차순 정렬한 뒤 (N - 이전 감소하는 수의 개수 합)번째 감소하는 수가

 

N번째 감소하는 수입니다.

 

모든 경우를 구할 때 num%10으로 앞자리보다 작은 값들을 오게하도록 재귀함수를 진행

자릿수만큼 수를 완성했을 때 List에 저장!

 

    static void search(long num, int size, int maxSize){
        //원하는 자릿수만큼 완성시
        if(size  == maxSize){
            list.add(num);	//완성 숫자 저장
            return;
        }
        //자릿수 증가, 앞자리와 비교하여 작은 수를 붙이는 과정
        for(int i=0;i<num%10;i++)
            search(num * 10 + i, size+1, maxSize);
    }

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 18

 

2. 감소하는 수가 증가하는 개수를 기준으로 가장 가까운 자릿수를 얻어서 N번째 감소하는 수를 탐색합니다.

 

가장 가까운 자릿수 찾기

 

0 ~ 9 : 9개

10 : 1개

20 : 2개

30 : 3개

= 15개

40 : 4개

= 19개

N(18) ≤ 19 만족!

 

18(N) - 15(40이전 감소하는 수의 경우) = 3

 

40으로 만들 수 있는 감소하는 3번째 수

 

40으로 만들 수 있는 감소하는 수의 모든 경우 오름차순 정렬

 

3번째 수 : 42

 

40

41

42

43

 

3. N번째 감소하는 수에 따른 결과를 출력합니다.

 

18(N)번째 감소하는 수 : 42

 

 42를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
  
• 감소하는 수의 만들 수 있는 경우를 더해서 가장 가까운 자릿수를 구합니다.
• 가장 가까운 자릿수에 search함수를 사용하여 모든 경우를 구하였습니다.
• Collections.sort를 이용하여 모든 경우를 오름차순 정렬합니다.
• N번째 감소하는 수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 자릿수와 앞자리를 기준으로 감소하는 수를 모든 경우를 구합니다.

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    static int[] arr;
    static ArrayList<Long> list;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        arr = new int[10];
        if(N < 10)	//N이 10미만일 때는 N이 N번째 감소하는 수
            bw.write(N + "");
        else {
            //십의 자리일 때 감소하는 수 개수 설정
            for (int i = 1; i < 10; i++)
                arr[i] = i;
            list = new ArrayList<>();
            //count : 감소하는 수 개수, size : 자릿수, index : 맨 앞자리 수
            int count = 9, size = 0, index = 0;
            boolean check = false;
            //감소하는 수 가장 가까운 자릿수 얻기
            while (!check && size != 9) {
                for (int i = 1; i < 10 - size; i++) {
                    count += arr[i];
                    if (count >= N) {	// N보다 커졌을 때
                        check = true;
                        count -= arr[i];
                        index = i + size;
                        break;
                    }else	//다음 자릿수 개수
                        arr[i] = arr[i-1] + arr[i];
                }
                if (!check)
                    size++;
            }
            //9876543210이 최대 감소하는 수, N번째 감소하는 수는 이보다 클 때
            if(size == 9)
                bw.write("-1");
            else{
                int dif = N - count;	//만들어야 하는 자릿수 i번째 수
                search(index, 0, size + 1);	//감소하는 모든 경우 만들기
                Collections.sort(list);	//오름차순 정렬
                bw.write(list.get(dif - 1) + "");	//i번째 수 BufferedWriter 저장
            }
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
    //자릿수와 앞자리에 따른 만들 수 있는 모든 경우의 수 구하는 재귀함수
    static void search(long num, int size, int maxSize){
        //원하는 자릿수만큼 완성시
        if(size  == maxSize){
            list.add(num);	//완성 숫자 저장
            return;
        }
        //자릿수 증가, 앞자리와 비교하여 작은 수를 붙이는 과정
        for(int i=0;i<num%10;i++)
            search(num * 10 + i, size+1, maxSize);
    }
}