(JAVA) 백준 1038번 : 감소하는 수

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

1038번: 감소하는 수

 

 

브루트 포스 문제이다.

 

감소하는 수 중 N번 째의 수를 찾는 문제.

 

 

핵심은

 

  -  한 자리의 수 i는 i번째 수에 해당한다.

  

  -  K 자리를 가지는 수 중 K 자리에 들어올 수는 최소 K - 1 이상이다.

 

 

ex.

 

2 자리를 가지는 수 중 최소 -> 10

4 자리를 가지는 수 중 최소 -> 3210

8 자리를 가지는 수 중 최소 -> 76543210

 

 

  -  최대 10자리까지 가능하다. 11자리부터는 한 자리 숫자의 개수를 초과한다.

  

 

10자리 -> 9876543210

 

 

  -  int 2차원배열을 만든 후 DP를 사용했다.

 

 

K는 K 자리를 가지는 수, i는 K 번째 자리에 해당하는 수(0 ~ 9) 라고 할 때,

 

result[K][i] = result[K][i - 1] + result[K - 1][i - 1]

 

result[K][i] 는 K번째 자리 수에 i가 들어왔을 때에 가능한 감소하는 수의 개수

 

 

그래서, 위 result를 구하면 N번 째에 해당하는 감소하는 수를 바로 구할 수 있다.

 

제가 그린 result 2차원 배열 값입니다...

그림이 이상하긴 한데

 

위 글과 그림을 번갈아보면 더 쉽게 이해하실 수 있을 것이다.

 

보라색 부분이 DP 공식에 해당.

 

값은 가능한 감소하는 수의 개수

 

 

이다.

 

 

 

 

 

매커니즘

---

  1.  이중 for문으로 DP 조건에 맞게 생성

 

  2.  1을 진행하면서 동시에 원소 하나씩 값을 더해가며 진행

    만약 이 값이 N(N번 째 감소하는 수) 보다 같거나 크면 [k][i] 에서 K 자리의 수는 i 가 된다.

 

  3.  2에서 조건을 만족하면 [k - 1][~] for문을 진행하며 해당 2번과 같이 진행한다.

    단, N 보다 같거나 큰 값이 아닌 N - SUM(원소 하나씩 더한 값) 과 비교를 한다.

    이를 첫 번째 자리 수를 찾을 때까지 반복한다. 만약 하나의 수도 만족하지 못하면 -1을 출력한다.

     

 

 

 

감사합니다.

 

 

소스코드

---

	package bruteforce;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Arrays;
	// 감소하는 수
	// 브루트 포스
	public class p1038 {
	static int dp[][];
	public static void main(String args[]) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	if(n < 10) { // 한 자리 수
	System.out.println(n);
	}
	else {
	dp = new int[11][10];
	Arrays.fill(dp[1], 1);
	for(int i = 2; i < dp.length; i++) {
	for(int j = 1; j < dp[1].length; j++) {
	dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
	}
	}
	String result = findNumber(n);
	result = result == null ? "-1" : result;
	System.out.println(result);
	}
	}
	// n번 째에 해당하는 숫자 찾기
	static String findNumber(int n) {
	int sum = 0;
	for(int i = 1; i < dp.length; i++) {
	for(int j = 1; j < dp[1].length; j++) {
	if(sum + dp[i][j] >= n) {
	return String.valueOf(j) + getDecreaseNumber(i - 1, n - sum);
	}
	sum += dp[i][j];
	}
	}
	return null;
	}
	// 재귀함수
	// 한 자리 씩 감소하면서 자리에 맞는 숫자 찾기
	static String getDecreaseNumber(int k, int sum) {
	if(sum == 0) {
	return "0";
	}
	int nowSum = 0;
	for(int j = 0; j < dp[1].length; j++) {
	if(nowSum + dp[k][j] >= sum) {
	if(k == 1) {
	return String.valueOf(j);
	}
	return String.valueOf(j) + getDecreaseNumber(k - 1, sum - nowSum);
	}
	else {
	nowSum += dp[k][j];
	}
	}
	return null;
	}
	}

view raw p1038.java hosted with ❤ by GitHub