첫 번째 시도
- 항상 순서가 정해져 있기 때문에 nCr, 즉 n개 중에 r개를 중복 없이 뽑는 경우의 수와 같다.
- 그래서 nCr을 통해 풀어봤지만, 시간이 오래걸린다.
- 틀리고 나서 규칙을 찾아보려고 함
- 다음과 같은 점화식 규칙을 찾음
- dp[i][j] : i 자리수의 최상위 자리수가 j인 범위의 감소하는 수 총합
- dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
- 괜히 0을 0번째라고 언급한 게 아님
- 맨 마지막 수인 9876543210은 1022번째 수(N)
- long long…
- 1021까지 계산한 후, 1022 부터는 수를 하나씩 감소하는 수인지를 확인해보는데 9000000000부터 9876543210까지 전부 확인하려하니 시간이 너무 오래 걸림
- 그래서 1022이면 9876543210을 리턴하도록 하드코딩해서 PASS함
- {0,..9} 라는 집합의 부분 집합 개수를 구하는 것이기 때문에 총 1024(2^10)개에서 공집합과 0을 제외하면 1022라는 수가 나온다.
- 2중 for문이 아닌 1중 for문으로 계산