(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을 출력한다.

     

 

 

 

감사합니다.

 

 

소스코드

---