문제

1시간 잡고 3문제 풀어야지 했는데 이문제만 2시간 잡고 있었다…. 결국 다른 풀이법을 이용해 내가 할 수 있는 방법으로 코드화했다.

문제 링크

문제 접근

  • 일단 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}의 각 부분 집합을 이용해 만들 수 있는 감소하는 수는 각각 1개이다.
  • 예를 들어, {1, 4, 7, 9} 라는 부분 집합을 이용해서 만들 수 있는 감소하는 수는 9741 단 하나이다.
  • 때문에 공집합을 제외한 부분 집합의 개수(2^10 - 1)가 총 만들 수 있는 경우의 수이다.(이 개수는 다른 블로그를 참고하면서 알게 됐다…)
  • 그렇게 많지 않은 감소하는 수를 다 찾아놓는다면 쉽게 답을 찾을 수 있을 것이다.
  • 그렇다면 어떻게 감소하는 수를 찾을 수 있을까?

모든 감소하는 수 찾기

  • 나는 감소하는 수를 찾기 위해서 DFS와 Sort를 이용했다.
  • num이라는 수를 받아서 그 수의 1의 자리 수보다 작은 수를 뒤에 붙여준다.
  • 이를 하나의 어레이에 저장한 후에 다시 새로 생긴 수로 위 반복했다.
  • 모든 수를 구하고 난 후에는 sort를 진행했다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;
long long n, cnt, dec[1024];

void dfs(long long num){
    long long val = num % 10, cur = num * 10;
    for(int i = 0; i < val; i++){
        dec[cnt++] = cur + i;
        dfs(cur + i);
    }
}
int main(){
    scanf("%lld", &n);
    for(int i = 0; i < 10; i++){
        dec[cnt++] = i;
        dfs(i);
    }
    sort(dec, dec+cnt);
    if(n < cnt)printf("%lld", dec[n]);
    else printf("-1");
}

느낀점

  • 이 문제에서 dfs를 통해 새로운 숫자를 만들게 되는데 이 과정에서 dp가 사용된다고 본 것 같다.
  • 아직 정말 가야할 길이 먼 것 같다.