좋은 방법이요?

일단 소문제 1부터 생각해 봅시다. N=5일 때 39번째 순열은 어떻게 표현 될까요?

맨 윗자리부터 채워 봅시다.

y (나머지 4자리) 네요.

4자리를 배열하는 가짓수는 4! = 24개죠.. 39는 24보다 큽니다. 따라서, 앞에 1은 안 들어오죠.

앞 자리가 1, 혹은 2인 가짓수는 몇 가지일까요? 24 + 24 = 48이겠죠..

따라서 앞자리는 2네요~

2 ? (나머지 3자리)

2 ? ? ? ? 은 25번째 부터 시작됩니다.

3자리를 배열하는 가짓수는 6가지입니다.

그렇다면

2 1 ? ? ? 은 25번째 부터 30번째까지 가겠죠? 당연히 아닙니다.

2 3 ? ? ? 은요? 31번째부터 36번째까지 가지 않나요? 당근 아니죠.

2 4 ? ? ? 은요? 37번째부터 42번째까지 나오는군요. 따라서 2 4 ? ? ? 입니다.

이런 식으로 끝 자리까지 재귀적으로 채워 나가시면 됩니다.

소문제 2는 어떻게 생각하면 될까요?

역시 5자리가 있고 이런 식으로 배열되어 있습니다.

3 5 4 2 1

이것은 몇 번째 순열일까요?

당연히. 1 ? ? ? ? 이랑 2 ? ? ? ? 보다는 뒤에 있겠죠.

1 ? ? ? ? 의 가짓수는 24. 2 ? ? ? ?의 가짓수도 24가지 입니다.

그러면 3 ? ? ? ? 중에서 찾아야 한다는 소린데요.

3 1 ? ? ? 보다는 뒤에 있죠?

역시 3 2 ? ? ? 보다도 뒤에 있고요 3 4 ? ? ? 보다 뒤에 있습니다.

이 세 가지 경우를 모두 합하면 18가지입니다.

역시 이것도 재귀적으로 돌려가면서 누적시켜가면서 찾으시면 되겠습니다.

사전순 찾기 문제와 비슷해 보이네요. 더 자세하게 알려드리면

그냥 답을 알려드리는 것이나 마찬가지라고 생각해요. 종이에 천천히 그려보시고, 차분하게 코딩해 보세요~

와! 알찬 답변 정말 감사합니다!

혹시 제 코드에는 어떤 에러가 있길래 시간 초과가 뜨는지 알 수 있을까요?

말 그대로 brute force를 써서

시간 초과가 뜹니다. 20!은 대충 계산해도 long long형으로 표현할 수 있는 정수값 최대치/4 정도 됩니다.

아 brute force로 문제를 풀이한게 시간 초과의 원인이었군요!

좋은 답변 감사합니다. 좋은 하루 되세요!