[백준/BOJ] 1038 감소하는 수

문제

출처 : https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

 

음이 아닌 정수의 가장 큰 자릿수 부터 가장 작은 자릿수까지 각 자릿수가 모두 감소하는 수를 감소하는 수라고 한다. 이 때, N번째 감소하는 수를 찾는 문제다.

 

---

풀이

N이 최대 1,000,000이길래 처음에는 DP로 생각했는데, 좀만 더 생각해보면 탐색횟수가 그렇게 크지 않다는 것을 알 수 있다. (DP식이 나오긴 하는걸로봐서 DP로 풀릴거 같긴 함)

 

음이 아닌 정수가 가능한 수는 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 총 10개다. 따라서 가장 큰 감소하는 수는 가능한 수를 큰 수부터 차례대로 배치한 9876543210이 된다.

 

각 자릿수를 하나의 칸으로 보자. 9876543210 은 총 10개의 칸이 되며, 찾는 수가 감소하는 수 이므로 N+1번째 칸은 N번째 칸보다 항상 작아야 한다. 따라서, 각 칸에 올 수 있는 수는 최악의 경우, 9*8*7*6*5*4*3*2*1 이 된다.

 

즉, 이 문제는 완전탐색으로도 풀린다.

 

논리는 다음과 같다.

1. 자릿수가 1일 때 부터, 10일 때 까지, 모든 감소하는 수를 탐색한다.

2. 자릿수가 0에 도달했을때(기저), 완전한 감소하는 수 가 하나 완성된것 이므로 N에 1을 빼준다.

위 과정을 N이 0이 될때까지 반복하면된다. (나는 코드 상에서 N이 -1이 될때까지로 구현했는데, 이유는 문제에서 '0'을 0번째 감소하는 수 로 생각하기 때문이다.)

 

주요 소스코드 (논리를 그대로 구현했다.)

	private void recur(int maxNum, int digit, long res){
		this.digitCheck[digit] = true;
		if(digit > 10 || this.res != -1) return;
		if(digit == 0){
			this.N--;
			if(this.N == -1) this.res = res;
			return;
		}
		if(maxNum < 0) return;
		for(int num = 0; num <= maxNum; num++) recur(num-1, digit-1, res+((long)Math.pow(10,digit-1)*num));
		if(!this.digitCheck[digit+1]) recur(9, digit+1, 0L);
	}

digitCheck는 이미 탐색한 digit(자릿수)를 재 방문하지 않도록 하기 위해 넣은 배열이다.

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1038%20%EA%B0%90%EC%86%8C%ED%95%98%EB%8A%94%20%EC%88%98/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃